Однажды мне в голову закралась довольно интересная идея: «Как компьютер складывает числа?». Тогда я начал размышлять над этим вопросом. Поскольку ЭВМ может обрабатывать только двоичные числа, ей нужно не только считать, но и переводить из десятичной системы в двоичную, и наоборот.
Таким образом, калькулятор должен уметь:
Складывать двоичные числа
Конвертировать двоичное число в десятичное
Конвертировать десятичное число в двоичное
Cуммирование двоичных чисел
Суммирование чисел в двоичной системе происходит по тем же правилам, что и в десятичной
0 + 0 = 02
1 + 0 = 12
0 + 1 = 12
1+1 = 102 (так как цифры 2 нет, нам надо перенести 1 в следующий разряд)
Исходя из этого, нужно сделать схему, которая удовлетворяет нашим условиям. Для этого нужны логические условия: и, или, исключающие или (and, or, xor соответственно)
and — логическая операция, возвращающая 1 только, если на вход было передано две единицы.
or — логическая операция, возвращающая 0 только, если на вход было передано два нуля.
xor — логическая операция, возвращающая 0, если на вход было передано два нуля или две единицы.
Для получения суммы двух чисел нам понадобиться xor. Так как 1 + 1 = 102, также понадобится число в следующем разряде, для этого подойдет and. Используя вышеперечисленные знания, можно сделать такую схему — полусумматор. Но он используется только для единиц, потому что не берет во внимание избыток из предыдущего разряда, или же бит переноса
А для десяток, сотен и т. д. используется сумматор.
Совместив первые две схемы, получим двухбитный сумматор
Эта схема позволяет складывать уже двухзначные числа. Мы можем бесконечно добавлять сумматоры и получать трех‑, четырехбитные сумматоры…
Конвертация десятичного числа в двоичное
Чтобы перевести десятичное число в двоичное, я решил использовать формат BCD (binary‑coded decimal). Для этого нам надо десятичное число перевести в BCD, и BCD в двоичное. Пример BCD числа может быть такой 1000 0011. В десятичном представлении это число равно 83. Каждые четыре бита означают свой разряд. Первые четыре бита кодируют десятки, а вторые единицы.
00112 = 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 0 + 0 + 2 + 1 = 310
01002 = 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0 = 8 + 0 + 0 + 0 = 810
Поскольку 0100 - это десятки ,а 0011 - это единицы, получается число 83
not - логическая операция, инвертирующая входной сигнал. Т.е. если приходит 0, то возвращается 1, и наоборот.
Я привел в пример схему шифратора он конвертирует десятичные числа в BCD. Но шифратору нужно добавить еще цифры от 0 до 9 на разряд, по такому же принципу. Если мы хотим вводить числа до 999, то нам понадобиться 30 элементов шифратора.
Итак, теперь калькулятор умеет конвертировать десятичные числа в BCD, но нам нужны двоичные числа. Для этого можно использовать алгоритм Double Dabble. Его можно описать так: двоичное число сдвигается влево один раз для каждого из своих битов. После каждого сдвига проверяются все цифры BCD, и к любой цифре BCD, которая в данный момент больше 4, добавляется 3.
Если перенести это на схему, то получиться так
В итоге, используя шифратор калькулятор конвертирует десятичное число в BCD и из BCD в двоичную систему, благодаря обратному алгоритму Double Dabble.
Конвертация двоичного числа в десятичное
Чтобы сделать такое преобразование, нужно использовать схему, описанную выше, но наоборот.
Двоичное число → BCD → Десятичное
Чтобы перевести из BCD в десятичную систему, понадобится дешифратор
Также как и с шифратором, нужно 10 схем на разряд с числами от 0 до 9.
Реализация
К сожалению, я не могу повторить это в жизни, но ко мне пришла идея имплементировать эти схемы в Minecraft. Так как в Minecraft есть редстоун и редстоуновый факел, в игре можно реализовать любую логику
Редстоун проводит сигнал, а редстоуновый факел инвертирует его. Теперь нужно создать логические операции.
Так выглядят not, and, or, xor соответственно.
В Minecraft есть возможность создание памяти. Верхний рычаг управляет лампой, а нижний за сохранение/перезапись
Принцип действия такой: пользователь вводит число от 0 до 9, в данном случае это 4. Сигнал активируется, и инвертируется, получается 0. 0 идет по медным блокам, но там где расположен факел он обратно инвертируется в 1. Сигнал переходит на желтую шерсть и вместе с еще тремя битами получается 01002, что равно четырем. Так надо закодировать каждое число от 0 до 9, правильно расставив факелы.
В дешифраторе сигнал идет по синей шерсти, поскольку я кодирую 9,а это 10012 первый бит должен быть 1, поэтому там стоит один факел, инвертирующий сигнал. Второй бит должен быть 0,а чтобы схема сработала правильно там находится два факела. Аналогично кодируем остальные биты. Если число подходит тому, которое мы кодировали сверху схемы, останется 0, в конце надо его инвертировать. Лампочка загорается и схема отдает число 9.
Разобравшись с основами редстоуна, надо сделать полноценную схему калькулятора.
Пользователь вводит число, шифратор преобразует его в BCD, и оно сохраняется в память. Далее пользователь включает переключатель чисел и вводит другое число, которое также конвертируется в BCD и помещается в ячейку памяти. Два числа превращаются в BIN и складываются в Сумматоре, после чего происходит переход из Bin в BCD,и из BCD в DEC. Когда все процессы закончены, число выводится пользователю.
Я хочу вводить трехзначные числа, а значит мне нужно 12 бит BCD. На выходе будет 10 бит BIN, а в сумматоре может стать 11 бит, что означает в конверторе BIN to BCD будет на выходе 16 бит, 3 из них будут всегда 0, и останется 13 бит.
Чтобы сделать Конвертор BIN to BCD, я решил использовать пару шифратор-дешифратор для прибавления трех, если число удовлетворяет условию «больше четырех».
Слева пара шифратор‑дешифратор в горизонтальном исполнении (вы видели их выше), а справа вертикальный. В калькуляторе я использовал именно вертикальный, из‑за его сравнительно небольших размеров в длину. Теперь нам нужно много таких пар шифраторов дешифраторов, чтобы сделать конвертор. Cмотрим на схему Double Dabble и повторяем ее, должно получится что‑то такое
Теперь нам нужен Конвертор BCD to BIN, принцип такой же.
Осталось сделать только экран.
Экран состоит из конвертора BCD to DEC (нижний слой) и из двух шифраторов. Верхний шифраторов отвечает
за области: f, a, b. Второй шифраторов управляет e,g,c,d.
Конвертор отдает десятичное число в два дешифратора, а они подают сигнал на лампы
Собрав все механизмы вместе мы получим это
Верхний ряд отвечает за сотни, средний за десятки, а нижний за единицы. Сейчас введено число 766. Левый верхний рычаг нужен для переключения числа, после ввода первого числа нужно переключить этот рычаг и вводить второе число.
Здесь можно посмотреть видео работы
Таким образом, получился такой калькулятор. Он полноценно работает, складывает трехзначные числа, но скорость оставляет желать лучшего это происходит, из‑за задержки в Minecraft на повторители и факела.
UPD:
Карта с калькулятором на версии 1.20.4