Если хочется низко-низкоуровневого программирования с битами и байтами

Сразу должен предупредить, что в отличие от предыдущих двух статей, здесь вы не встретите каких-то сведений, имеющих практическое значение для 1С-ника. Статья имеет скорее ностальгически-познавательный характер.

Итак, начнем. Не будем останавливаться на том, что такое двоичная система, и почему именно она заняла лидирующее положение в цифровой вычислительной технике (так было не всегда, и в связи это не так до сих пор). Ниже будет применяться следующая форма записи: 2310=101112.

Как известно, байт - это 8 бит. Количество различных чисел, которые можно задать с помощью 1 байта = 2⁸ = 256: 010..25510 или 000000002..111111112. Первый бит, тот который крайний слева, называется старшим, последний, соответственно, младшим. Умножение числа на 2 (основание системы счисления), это просто дописывание в конце числа "0", или, что то же, сдвиг числа на один разряд в сторону старшего бита: 210 -> 410: 000000102 -> 000001002.  Аналогично, деление на 2 - сдвиг в обратную сторону.

Помните в 1 классе таблицу сложения? Так вот, в двоичной системе счисления она весьма невелика:

В последней строке у нас получилось число 102, старший бит которого равен единице. При поразрядном сложении ("столбиком") больших чисел в двоичной системе этот бит переноса - то самое значение, которое "в уме" ("ноль пишем, один в уме"). Он будет участвовать в сложении следующих разрядов:

Вот сложение 2310 + 2910 = 5210

  00010111  
+ 00011101 
= 00110100

Реалии цифровой электроники таковы, что на полупроводниковой элементной базе легко воспроизвести булевы функции - И, ИЛИ, НЕ. Также легко реализуются поразрядные сдвиги влево и вправо.

Вот схематичные примеры электронных схем на транзисторах (источник - яндекс-картинки):

Представив "1" и "0" как "Истина" и "Ложь" легко эмулировать сложение двух бит логическими функциями.

Для первой таблицы (без учета бита переноса предыдущего сложения):

БитПереноса = БитА И БитБ;
БитСумма = (БитА И Не БитБ) Или (Не БитА И БитБ);

С учетом предыдущего бита переноса:

НовыйБитПереноса = БитА И БитБ Или (БитА Или БитБ) И  БитПереноса;
БитСумма = (БитА Или БитБ Или БитПереноса) И Не НовыйБитПереноса Или БитА И БитБ И БитПереноса;

Таким образом, последовательно выполняя поразрядное сложение двух чисел (аналог "столбика"), мы найдем все биты суммы этих чисел. Реализуем этот алгоритм для однобайтных чисел, воспользовавшись платформенными функциями работы с двоичными данными.

Функция ДвоичнаяСумма(Знач А, Знач Б)
	Сумма = 0;
	БитПереноса = Ложь;	
	Для НомерБита = 0 По 7 Цикл  
		БитА = ПроверитьБит(А, НомерБита);
		БитБ = ПроверитьБит(Б, НомерБита);
		НовыйБитПереноса = БитА И БитБ Или (БитА Или БитБ) И  БитПереноса;
		БитСумма = (БитА Или БитБ Или БитПереноса) И Не НовыйБитПереноса Или БитА И БитБ И БитПереноса;
		БитПереноса = НовыйБитПереноса;
		Сумма = УстановитьБит(Сумма, НомерБита, БитСумма);
	КонецЦикла; 		
	Возврат Сумма;
КонецФункции 

Функция ДвоичнаяСумма(Знач А, Знач Б)
	
	Пока Б Цикл
		БитыПереноса = ПобитовыйСдвигВлево(ПобитовоеИ(А, Б), 1);
		А = ПобитовоеИсключительноеИли(А ,Б);
		Б = БитыПереноса;
	КонецЦикла;
	
    Возврат А;
КонецФункции;

Что получится, если мы попытаемся сложить два числа 20010 и 20010?

   11001000
+  11001000 
= 110010000

Как видим, результат занимает 9 бит, что не помещается в байте! Если старший бит будет потерян, то вместо 400 у нас получится 144. Этот эффект хорошо известен программистам на языке ассемблера и Си, он называется "переполнение". Как правило, программист вынужден контролировать возникновение таких ситуаций. К счастью, разработчики на высокоуровневых языках, в том числе 1С, избавлены от проявления ошибок, связанных с забытым контролем переполнения.

Со сложением разобрались, а как происходит вычитание? Очень просто, вычитание меняется на сложение с противоположным слагаемым А - Б = А + (-Б).  А как тогда представлены отрицательные числа? А вот с этим не очень просто. Очевидная идея - использовать под знак старший бит. Пусть, если он равен 1, то это будет отрицательное число, т.е. -210=100000102. Правда, мы тем самым более чем вдвое сужаем диапазон возможных положительных значений, представляемых байтом: -12710..+12710,и получаем два вида ноля: -0 и +0. Тем не менее, такой способ кодирования отрицательных чисел (он называется прямым) выглядит логичным, наглядным, но... Что будет если вычислить 210 - 210 = 210 + (-210)?

  00000010
+ 10000010
= 10000100

100001002 = -410, а не 010, как следовало бы ожидать. Так что прямой код нам не очень-то подходит для нашей арифметики. Для этого был придуман дополнительный код. Положительное число в дополнительном коде выглядит как обычно. Чтобы положительное число превратить в отрицательное в дополнительном коде, необходимо инвертировать в нем все биты и прибавить единицу. 210 -> -210: 000000102 -> 111111102. Понятно, что чтобы представить отрицательное число в дополнительном коде необходимо сначала взять модуль этого числа, и эту операцию проводить над ним.

Результат = ДвоичнаяСумма(ПобитовоеНе( -А), 1); // считаем, что А было отрицательным числом

И тогда 210 + (- 210)

   00000010
+  11111110
= 100000000

Если не считать возникшего переполнения (а его в данном случае считать и не нужно), мы получили то что требовалось: 000000002. Надо отметить два момента: при использовании дополнительного кода диапазон возможных значений байта становиться равным -12810..12710 = 100000002..011111112. Программисты на Си наверняка помнят несимметричные диапазоны знаковых целых типов: -128..127, -32768..32767 и т.п. - причина именно в дополнительном коде. Существует еще обратный код - в нем биты инвертируются без добавления единицы, он немного более нагляден, но в этом случае единицу надо добавлять при каждом сложении. При работе с числами в  дополнительном коде необходимо осуществлять контроль переполнения: при сложении двух положительных чисел старший бит не должен равняться 1, при сложении двух отрицательных - не должен равняться 0, при сложении чисел разных знаков возможное переполнение учитывать не нужно, оно чисто техническое и не играет роли. 

Так, со сложением и вычитанием разобрались, на очереди умножение.

Таблица Пифагора для двоичной системы наверняка бы понравилась всем школьникам:

Умножение столбиком ничуть не отличается от школьного, только умножение одного множителя на каждую цифру другого (т.е. единицу или ноль) - элементарно.

2310 * 2910 = 66710

       00010111  
*      00011101 
       00010111 
      00000000 
     00010111 
    00010111  
   00010111     
=  001010011011

Очевидно, что результат длиннее чем любой из множителей, но не более чем вдвое. Поэтому при умножении двух однобайтных чисел для произведения нужно зарезервировать 2 байта.

Алгоритм на основе умножения столбиком прост - в цикле побитово сдвигаем один из множителей влево, если соответствующий бит другого множителя равен 1, то добавляем этот сдвинутый множитель к результату.

Произведение = 0;
Для НомерБита = 0 По 7 Цикл  
	Если ПроверитьБит(А, НомерБита) Тогда   
		Произведение = ДвоичнаяСумма(Произведение, Б);			
	КонецЕсли; 
	Б = ПобитовыйСдвигВлево(Б, 1);
КонецЦикла; 

На каждом шаге необходимо проверять переполнение. Перед умножением все числа надо привести к положительным, т.е. взять модуль для отрицательных. Если знаки множителей одинаковы, то результат должен быть положительный, иначе результат должен быть отрицательным, требуется перевести его в дополнительный код. Существует и другой алгоритм умножения, не требующий взятия модуля - алгоритм Бута, но он находится за рамками данной статьи. 

А теперь - деление.

66710 / 2310 = 2910

Вспомним школьное деление уголком

1010011011       10111 
 10111           11101 
 100101 
  10111
   11100 
   10111
    01011
    00000
     10111
     10111
         0   

Алгоритм тоже несложен, для А / Б:

Частное = 0;
Сдвиг = 0;
Пока А > Б Цикл
	Б = ПобитовыйСдвигВлево(Б, 1);
	Сдвиг = Сдвиг + 1;
КонецЦикла;		
Для Счетчик = 0 По Сдвиг Цикл  
	Частное = ПобитовыйСдвигВлево(Частное, 1); 
	Если А >= Б Тогда   
		А = А - Б;
		Частное = УстановитьБит(Частное, 0, Истина);		
	КонецЕсли; 
	Б = ПобитовыйСдвигВправо(Б, 1);			
КонецЦикла; 		

Все что было сказано о знаках для умножения, верно и для деления. Деление в алгоритме - целочисленное, т.е. если делимое не делится нацело, от него остается остаток. Разумеется, дополнительно надо контролировать, чтобы делитель не был равен 0.

Вот так можно эмулировать элементарные арифметические операции с помощью логических операций и сдвига. Зачем это нужно 1С-нику? Да в общем-то, для решения учетных задач это бесполезно. Но знания бесполезными не бывают, каждый квалифицированный IT-шник должен иметь представление, что находится "под капотом" компьютера на самом низком уровне. Энтузиасты делают калькуляторы не только на транзисторах, но и из г-на и палок палок и шариков, и даже в MineCraft. 1С уже давно вышла за рамки только бухгалтерских задач, платформенные функции для работы с двоичными данными позволяют решать задачи, ранее решаемые с помощью "настоящих" языков. Если погрузиться в эту область, то можно обнаружить много интересного: коды Хэмминга и Рида-Соломона(исправляющие ошибки), коды Хаффмана (сжатие данных), коды Грея (защита от помех при передаче данных), генерация и чтение штрих- и двумерных кодов (Code39, QR-код), дискретное логарифмирование (шифрование и ЭЦП) и многое другое.

К статье приложена обработка, в которой реализованы вышеописанные алгоритмы. В обработке используются 4-байтные (32-разрядные) числа. Тестировалась на платформе 1С:Предприятие 8.3 (8.3.21.1393)

На этом всё. Как всегда, приветствуются замечания / дополнения / комментарии.

Предыдущие статьи:

• Если хочется функционального программирования с функциями высшего порядка и map, filter, reduce
• Если хочется ООП с наследованием и полиморфизмом