Pull to refresh

Brainfuck — вывод в десятичном формате

Reading time 2 min
Views 3.1K
В качестве первой задачки для реализации на brainfuck я решил взять, казалось бы, простое упражнение — вывести в десятичном формате записанное на ленте 4-байтовое число. Задачка оказалась интересной, особенно, если учесть, что дублировать код (и использовать, что число именно 4-байтовое) мне хотелось как можно меньше, а больше пользоваться циклами.

Сразу было видно, что есть два разных подхода — либо пытатьтся делить исходное число с остатком на 10, и составлять цифры из полученных остатков, либо формировать десятичное число, умножая его на 2 и при необходимости прибавляя единицу. Поигравшись со вторым вариантом, и обнаружив, что биты поступают не в том порядке, в каком надо, вернулся к первому варианту.



Проблем было две — первое: избежать возникновения ведущих нулей, второе: написать деление с остатком «длинного» числа на 10. Вторая задача, очевидно, сводится к делению двухбайтового числа, меньшего 2560… Но перейдем сразу к программе.

Сначала ввод. В принципе, он не нужен (по условию, число уже записано на ленте), но надо же как-то отлаживать

,>,>,>,<<<

Чтобы можно было использовать цикл по исходным данным, введем дополнительную разметку

<+>
>>>[->>>+<<<]<
[->>+<<]<
[->+<]
+>>+>>+

Между байтами исходного числа и слева от левого байта стоят единицы. Каретка — на самой правой единице (между двумя младшими байтами). Начинаем главный цикл. С этого момента длина исходных данных нигде не используется.

Сначала найдем начало числа

[[<<]>>

Теперь будем сдвигать каждую цифру на 4 ячейки влево, и на освободившемся пространстве делить число, составленное из предыдущего остатка и новой цифры, на 10:

[->[-<<<<+>>>>]<<<<<
[->>+>+<<<]>>+
[-<[->>+>++++++++++<[->->+<<]+>[-<[-]>]<[->>[-]<<<<<+>>>]>>[-<<+>>]<<<<]->]

Здесь используется тот факт, что (a*256+b)/10=((a*255+b)+a)/10, и что a<10.

После того, как частное и остаток найдены, надо проверить — не получился ли ведущий ноль. Если получился, то метку «1» между найденным и следующим байтами не ставим.

<+<[->+>+<<]
>>[-<<[-]+>>]<<<<[->>[-]+>>+<<<<]>>>>
[-<<<<+>>>>]>[-<+>]>>>]

Когда число кончилось, последний найденный остаток — это новая цифра. Приписываем ее к строке вывода

<++++++[->++++++++<]<<<[->>>>+<<<<]

и сдвигаем цифры найденного на этом шагу частного на 3 байта вправо (чтобы они были на правильном расстоянии от строки вывода)

<<[->[->>>+<<<]>>+<<<<<]>>>>>]

Если оказалось, что частного нет, цикл закончен — и можно выводить строку

>[.>]+++++++++++++.---.

Вот и все.

Получилось как-то громоздко — наверное, многих возможностей я еще не вижу.

Может быть, вариант с удвоением был бы лучше — но для него исходные цифры надо было бы не делить, и умножать на 2, и работать с битом переноса. Надо будет попробовать. Но этот вариант будет работать только когда число состояний «байта» — степень двойки (в приведенном выше коде этот факт не используется, программа будет работать с любым числом состояний, большим 10).
Tags:
Hubs:
-1
Comments 12
Comments Comments 12

Articles