Forth: Как найти и отделить самую правую единицу в двоичном числе

Листая одну старую книжку по древнему языку программирования Форт [1], я наткнулся на такой фрагмент, в котором меня заинтересовало слово LAST1:

Ну и в соответствии с философией Forth — отсекай всё лишнее, делай систему настолько простой, чтобы ты мог понять её до последнего транзистора и бита, я решил разобраться и сам, и поделиться своим разбором с вами.

КМБ‑Forth, который «деды» могут пропустить

Если вы не имели дел с языком программирования Forth, то я для вас поясню, что значит

: LAST1 DUP DUP 1- XOR AND ;

• Вся эта вышеприведённая строка — одно «слово». А «словом» в Форте называется что‑то вроде вызываемой функции или подпрограммы. Начинается определение «слова» с двоеточия, а заканчивается точкой с запятой. Первый после двоеточия элемент — «имя функции/подпрограммы» (в нашем случае это LAST1). Хотя в Форте такое «имя» как раз и принято называть «словом».

• Все элементы языка должны быть отделены друг от друга пробелами.

• Слово (операция) DUP дублирует самый верхний элемент стека. В нашем случае — число. Две операции DUP обеспечивают целых три копии исходного числа, лежащих на стеке (зачем нам три копии одного и того же числа — расскажу далее).

• Слово «1-» — быстрый вариант вычитания единицы. Почти как «--» в Си. Здесь нам нужно лишь понимать, что для своей работы (вычитания единицы) слово «1-» берёт из стека первое попавшееся самое верхнее число, а потом кладёт туда же, на верхушку стека, результат.

• XOR и AND — одноимённые логические операции. И они для своей работы берут числа из стека. И они нахлобучивают результаты своей жизнедеятельности на его макушку.

• Вообще, все промежуточные результаты сохраняются в стеке. Через него же передаются и все параметры «функций» («слов»).

Как видите, всё просто.

Погнали разбираться!

Итак, представьте, что у нас есть число (допустим, 12), которое, конечно же, можно записать в двоичной системе счисления при помощи нулей и единиц:

1 1 0 0

Наша задача — найти в нём самую правую единичку и оставить только её, а всё остальное стереть («обнулить»). «Всё остальное», это, конечно же, только левая (старшая) часть числа. Правая и так заполнена нулями до самой искомой единицы. Тут уже, как говорится, «лишь бы не испортить».

В нашем числе 12 самая правая единичка — третья слева (или вторая справа). В десятичной системе счисления «вес» её разряда равен четырём (4), поэтому и ожидаемый ответ должен быть равен 4 (в двоичном виде это 0 1 0 0).

Зачем это вообще нужно? (Практический смысл)

В программировании это очень полезный трюк. Вот пара причин, для чего это может понадобиться:

1. Быстрый подсчет единиц (алгоритм Брайана Кернигана): Если вам нужно посчитать, сколько единиц в числе (в нашем примере их две), вы можете в цикле находить крайнюю правую единицу, а потом вычитать получившееся число из исходного:

1.1. 12 — 4 = 8 (в двоичном представлении 1 0 0 0).\

1.2. Находим крайнюю правую единицу у восьми (8), получаем 8.
Вычитаем: 8 — 8 = 0. Цикл можно заканчивать. В цикле мы «крутились» 2 раза — значит, в числе 12 — две единицы. Обычно данный метод работает быстрее, нежели проверка каждого бита по очереди.

2. Работа с битовыми масками (например, дерево Фенвика): В сложных алгоритмах (например, в структурах данных для быстрого поиска сумм) нужно знать, какой длины «блок» данных соответствует текущему числу. «Поиск крайней единицы» мгновенно дает эту информацию, потому что в двоичном дереве вес младшего бита равен размеру блока. Позиция самой правой единицы в индексе строго определяет шаг алгоритма: её десятичное значение (например, 4 для 0100 или 2 для 0110) в точности совпадает с количеством элементов, за которые отвечает текущая ячейка. Битовая операция X & ‑X изолирует этот бит буквально за один такт процессора, позволяя мгновенно определять границы блоков без циклов и лишней памяти.

Итак, чтобы найти крайнюю справа единицу, нужно выполнить три шага.

Шаг 1. Ищем богатого спонсора, или Поиск первой значимой единицы при помощи вычитания

Итак, вычитание единицы, это как будто бы поиск самой первой единицы справа.
Но с какого перепугу?!

Смотрите. Нам нужно как‑то «пометить» место, где находится наша искомая единичка. Но как это сделать? Как процессору объяснить, что нам нужно? Для его электронных схем, откровенно говоря, особой разницы нет — единица в ячейке памяти, или ноль. Ячейка памяти ведь физически не меняется. В ней лишь может храниться электрический заряд, а может и не храниться. Ну или её простая транзисторная схема может находиться в одном из двух стабильных состояний. Но ни одно из них не лучше и не хуже другого. Это мы, люди, наделяем эти состояния нужным нам смыслом.

Так вот, отыскать первое вхождение единицы мы можем с помощью банальной арифметики — вычитанием самого маленького значимого числа из исходного числа. Если хорошенько подумать и вспомнить правила вычитания, то вы поймёте, что по сути, эта операция — не что иное, как способ пройтись по уменьшаемому справа налево, дойти до первой встречной единицы и оставить после себя определённый (а точнее, инверсионный) след. Система счисления при этом, не имеет никакого значения. И кстати, этот след мы потом превратим в шаблон‑маску, но не будем забегать вперёд и пока просто посмотрим, как работает этот своеобразный «битовый поиск»:

Возьмём наше число 12 (1 1 0 0), вычтем из него 1 и получим 11 (1 0 1 1). Нули справа стали единицами, а та самая, первая с правого края единица стала нулём. Как мы дошли до жизни такой?

Да также, как и всегда (ну, то есть, в других системах счисления). Представьте, что мы идём по исходному числу 12 (1 1 0 0) справа налево и упорно пытаемся вычесть одну единственную единичку — самое маленькое из значимых чисел:

• Сначала мы стучимся в самую маленькую дверцу крайнего правого и самого младшего из разрядов искомого числа, и говорим ему: «А займи‑ка нам, братец, одну ма‑а‑ленькую единичку?» — а он говорит: «Я бы и рад, да пуст совсем!».

• Тогда мы идём дальше влево, ко второму более весомому разряду, стучимся в его дверцу размером побольше и тоже спрашиваем: «А не займёшь ли ты нам, братец, одну самую малую единичку?» А он отвечает: «Я бы и рад, так ведь и у меня пусто!».

• Тогда мы идём к ещё более могучему третьему разряду, стучим в его массивную дверь и тоже просим: «Братец, займи единичку! Вижу, она есть у тебя!» И третий разряд охотно отвечает: «Да бери конечно! Правда, эта единичка — это всё, что у меня есть. Но зато смотри какая она весомая и жирная!.. И тебе хватит, и всем нашим братьям помладше!».

И вот тут и происходит самое интересное: единица из третьего разряда — такая большая и весомая, что её хватает и «попрошайке‑вычитаемому», и двум младшим разрядам, благодаря чему те самые два крайних правых нуля наполняются единицами. Однако сам третий разряд, растративший свою единицу на остальных, остался ни с чем. То есть, совсем потерял свой вес и стал нулём.

Вот так это выглядит схематично: 12: (1 1 0 0) —1→ (1 0 1 1):11

А вот самый старший четвёртый разряд остался со своей единицей — что называется, «при своих». До него попрошайка‑вычитаемое просто не дошёл. И это тоже очень важный элемент понимания принципа работы «поиска первой значимой единицы вычитанием».

Вот как образовался инверсионный след: Всё, что было правее искомой единицы, и она сама, изменило свои значения на противоположные. А левее искомой единицы — ничего не изменилось.

Простыми словами я бы смысл всей вышеназванной операции описал так:
вычитание единицы из искомого числа находит первый встречный ненулевой разряд и «успокаивается». Образовавшееся при этом число представляет из себя некий гибрид из инвертированной левой и неизменной правой частей.

Шаг 2. Позиционное разделение исходного числа

На этом этапе мы будем использовать логическую операцию XOR (исключающее ИЛИ), которую можно охарактеризовать как «детектор изменений».

Правило у неё очень простое: ставить единицу там, где биты разные, и ноль — где одинаковые

Мы же будем использовать XOR‑логику в качестве позиционного разделителя исходного числа, потому что помимо этого самого числа, предусмотрительно продублированного и лежащего до поры до времени в стеке, у нас есть и «волшебное гибридное число», содержащее как не изменённую старшую часть, так и инвертированную (то есть, изменённую донельзя) — младшую. Благодаря этому числу, XOR пометит нулями всё, что было ДО искомой единицы, ибо будет сравнивать исходные разряды с теми, которые не изменялось вычитанием (левая часть числа), а позицию самой искомой единицы и всё что правее неё, XOR отметит единицами (то есть маскирует), потому что по этой части числа «прошлось» вычитание.

Где «отметит»?

В новом числе, называемом маскою.

Теперь давайте смотреть на работу XOR, что называется, «в прямом эфире»:

Итог операции — маска, являющаяся картой изменённых разрядов.
Ноль слева — «здесь мы ничего не трогали».
Единицы справа и в позиции искомого разряда с единицей — здесь «наследило вычитание».

Маска как будто бы провела линию ровно по нашей искомой единичке: всё, что левее, закрыто нулями, всё, что на ней и правее — открыто единицами.

Шаг 3. «Выдавливаем» искомый разряд

К настоящему моменту на дне стека у нас самое‑самое первое и самое‑самое оригинальное (а не какие‑то там «дубликаты») искомое число, а поверх него, на вершине — «хитрая» маска‑разделитель, на конструирование которой и были потрачены все дубликаты исходного числа. И чтобы понять, что и как нам теперь с этими двумя числами делать, давай посмотрим на них:

Ну вот! Теперь же всё очевидно! Задача нашей маски — пропустить всю младшую часть исходного числа строго по «линии» искомого разряда (первого справа, содержащего значимую единицу) и не пропустить ничего левее искомого разряда. И, как мы видим, маска прекрасно справится с этой задачей: справа можно всё пропускать, потому что там сплошные нули до самого искомого разряда, включая его. А для правой части уже в разрядах самой маски «блокирующие нули».

Всё чего нам не хватает, это подходящей логической операции. Очень строгой — которая бы отсеивала любое несовпадение в параллельных разрядах, а также ноль в разряде. Логическая операция, которая воспринимала бы только две единицы в обоих сравниваемых разрядах!

И такая логическая операция есть у нас. Имя ей — AND.
AND выдаёт единицу только тогда, когда в одних и тех же разрядах И исходного числа, И маски, стоят единицы. Во всех остальных случаях AND будет выдавать ноль.

Вот её таблица истинности:

Теперь схема работы AND над исходным числом и маской:

Как видите, логика работы AND проста и незамысловата: используя нули маски, AND обнуляет старшую часть числа — перед искомой единицей. Потому что она нам не нужна. При помощи «младших единиц» маски она «выдавливает» из всей правой части числа искомую единицу. Тут уже нули правой‑младшей части числа как будто бы работают на нас, не позволяя единицам маски «пролезть» в итоговый результат. Вот и получается, что единственный, кто может пройти через строгое сито логической‑И, это искомая единица.
Впрочем, я, кажется, уже повторяюсь.

Итак, мы получили число, содержащее исключительно одну единственную единицу, в самом первом по счёту справа разряде: 0 1 0 0 (4), а большего нам и не нужно.

Коротко, в три строчки

1. Вычитание единицы, чтобы найти самый первый разряд, содержащий единицу и пометить путь к этому разряду.

2. XOR, чтобы сравнить «было» и «стало», и нарисовать карту изменений: «нули» — там, где ничего не трогали (левее единицы), «единицы» — там, где трогали (крайняя правая единица и правее неё. И всё это, чтобы превратить след от вычитания (он же — путь к искомой единице) в маску‑разделитель.

3. AND — накладывает карту изменений (маску) на исходное число и оставляет только ту единственную единицу, которая совпала с «открытой» зоной — для того чтобы вырезать из числа ровно то, что мы искали — самую первую с правой стороны числа единицу.

Вот так, тремя простыми шагами, слово LAST1 находит самую правую единичку в любом числе.

В качестве домашнего задания

Напишите более оптимальную версию слова LAST1 для Forth‑системы, в которой есть слово NEGATE, меняющее знак числа на противоположный. Подсказку о том, как можно было бы это сделать, внимательный читатель найдёт в тексте данной главы.

Вместо ЗАКЛЮЧЕНИЯ, или Отложенное ВВЕДЕНИЕ

Зачем Forth и кому он нынче сдался?

Мне почему‑то кажется, что если спросить современного разработчика о Форте, то в лучшем случае мы услышим от него, что мол, был такой древний язык программирования (ЯП), на котором когда‑то программировали компьютеры обсерваторий, но теперь это один из забытых и мёртвых ЯП. Действительно, Чак Мур создавал Форт, в том числе, и для управления телескопами, но область применения придуманного им языка быстро вышла далеко за рамки астрономии. Довольно часто автономные системы управления советских атомных ледоколов, бортовые компьютеры космических аппаратов (вроде зонда Rosetta) и глубоководных исследовательских станций, годами работали на Форте. В условиях, где отказ цифровой автоматики означал катастрофу, Форт ценили за предельную надёжность и компактность: его «компилирующий интерпретатор» можно было разместить в нескольких килобайтах памяти, и он не зависал.

Не потому что был каким‑то особенным, а потому что был просто и однозначно задуман. А ещё — потому что позволял писать и отлаживать ПО прямо на том же железе, на котором ему потом было суждено работать десятилетиями.

А ещё, потому что именно с Forth возможен голливудский сценарий, когда бородатый борт‑инженер влазит в ПО компьютера полуживой космической станции и перенаправляет информационные и энергетически потоки с уцелевших второстепенных систем на жизненно важные. А с прошивкой, скомпилированной и намертво защитой в память бортового компьютера в стенах лаборатории — нет.

В наши дни, когда гигабайты вполне годного кода генерятся нейросетями буквально за считанные минуты, использование труда программиста, да ещё и на Форт, может показаться лютым анахронизмом. Но только не в сфере критически важной инфраструктуры вроде ПО атомных станций или систем жизнеобеспечения. В этих сферах, слава Богу, слепо доверяться искусственному интеллекту пока никто не готов. Не мне вам рассказывать о том, как ИИ может галлюцинировать. Не мне вам рассказывать, сколько слоёв абстракции, виртуальных машин и чужих библиотек скрывает под собой код современных языков высокого уровня. В критически важных системах нужна абсолютная предсказуемость: программист должен точно знать, сколько тактов или микросекунд будет исполняться тот или иной фрагмент программы. Форт даёт этот контроль, поскольку он прозрачен чуть ли не до уровня транзисторов.

Сегодня Forth, как мне кажется, переживает определённый ренессанс, и связано это с лавинообразным распространением микроконтроллеров. На дешёвых чипах с жестко ограниченной памятью и скромными вычислительными ресурсами Форт способен в одиночку заменить и операционную систему, и среду выполнения, не погружая пользователя в пучину Ассемблера.

При этом он даёт разработчику уникальное преимущество — интерактивность. В отличие от классического цикла разработки на C (написал код — скомпилировал — прошил чип — проверил), Форт позволяет общаться с железом напрямую через терминал в реальном времени: вы можете прямо «на лету» протестировать работу конкретного датчика или изменить логику функции. И в отличие от операционных систем (даже реального времени) эта интерактивность почти ничего не стоит. По уровню удобства и интерактивности для современных микроконтроллеров Форт сравним с MicroPython, но при этом он работает в разы быстрее, обходится без тяжелой виртуальной машины и оставляет программисту полный контроль над аппаратной частью.

Ради чего было весь этот «огород городить»?

В современных высокоуровневых языках программирования вышеописанные фокусы на уровне отдельных битов требуются редко — компиляторы отлично справляются с этим сами. Более того, у некоторых CISC‑процессоров команда поиска крайней единицы реализована аппаратно.

Тем не менее, подобные низкоуровневые примеры полезны для понимания базовой архитектуры любых вычислительных систем. Они наглядно показывают, что логика работы процессора — это не абстракция, а физический процесс переноса разрядов, который подчиняется строгим математическим правилам. И понимание того, как именно вычитание единицы меняет структуру числа, что на практике делают две из трёх базовых логических операций, помогает лучше ориентироваться в том, как компьютер обрабатывает данные на самом деле.

Если у вас есть свои варианты оптимизации этой операции или интересные примеры использования подобных битовых масок в современных задачах, делитесь ими в комментариях. Я заранее благодарен всем за конструктивные комментарии.

Литература

1. Бураго А. Ю., Кириллин В. А., Романовский И. В. Форт — язык для микропроцессоров. Л.: Знание, 1989. 36 с.