Остановится ли? Часть II (Задача)

Условие задачи такое же, как и в предыдущей, но Вы можете использовать только язык программирования Brainf**k. Вывод программы должен содержать ровно 1 символ — ответ на вопрос («Y» или «N»).

Решение:
Будем теперь реализовывать проверку, является ли число n степенью двойки, на языке Brainf*ck. Первый этап – ввод числа. Так как ограничение довольно большое (), то хранить это число придется поразрядно.
>> ,+[>+++++++[-<------->]+>>,+]<<-<[+]
Отступим перед вводом две ячейки – они нам понадобятся в дальнейшем (вместо этого могли бы использовать две ячейки с отрицательными адресами, но в интерпретаторе bff-1.0.3.1 есть ошибка: они не заполняются нулями).
После каждой введенной цифры будем записывать специальную метку и оставлять пустую ячейку:

Метки впоследствии помогут нам точно определять границы числа. В качестве них используем единицу. Также, так как при вводе считывается код символа, а не сама цифра, для удобства вычтем код символа '0' (48).
В последнем «фиктивном» разряде будем накапливать остаток (сначала оставим ячейку пустой).

<<[<<<]>>>
После ввода «откатимся» к началу числа.

Далее идет сам алгоритм: будем целочисленно делить число на 2, пока оно не обнулится (длинная арифметика).
Начиная с первой цифры (старшего разряда):
[
[<[<<]>[->>>>]<] >>>
Этот фрагмент не выполнится на первой итерации, только на последующих: удалим лидирующие нули (сотрем метки обнуленных разрядов).

[
<[->>+<<] + >>
Перенесем цифру в пустую ячейку справа от метки, а в исходную ячейку положим резервное значение 1, чтобы в любом случае иметь возможность «откатиться» до нее.

[
->++++++++++< [->----------<<<+>-]
Пока не обнулим разряд, будем вычитать 2 и в исходную ячейку прибавлять 1.
Более детально: если удалось вычесть 2, то временно обнулим метку.

Если цифра по-прежнему больше нуля, восстановим метку и повторим:
<[<]>>[-]+ >
]
Если же цифра была нечетная, и на данном шаге мы уменьшили ее до единицы, то обнулим ее и совершим перенос разряда: в следующий разряд числа прибавим 10 (при этом метка не обнуляется).

<<-> >>>
]
Вычтем обратно из исходной ячейки «резервную» единицу и перейдем к следующему разряду (повторим с пункта 1).

<<<[<<<]>>>
]
Достигнута последняя цифра – число поделено на 2. Если она была нечетная, то в результате мы прибавили 10 в следующий «фиктивный» разряд – в этой ячейке накапливается суммарный остаток от деления.
«Откатимся» к первой цифре числа и повторим деление (с пункта 0).

<<< +++++[-<--<++>>]<<+[>>++++++++<[>->]<[<]>-] >>+.
Когда число целиком обнулилось (не осталось ни одной метки), проверяем, чему равен накопленный остаток: если 10 (только за счет последней единицы), то n – степень двойки, выводим 'Y', если же больше – выводим 'N'.

Автор: ymushnikova

Источник