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

01.12.22

Разработка - Математика и алгоритмы

Все знают, что подавляющее большинство современных компьютеров работает в двоичном коде, т.е. оперирует всего двумя значениями - битами - "0" и "1". Потом из них складываются байты, слова, кило-, мега- и гигабайты etc. Но что происходит внутри процессора, как именно обрабатываются двоичные числа, например выполняются арифметические операции? Об этом — в публикации. Статья, я думаю, будет особенно интересна тем читателям, у которых во время обучения не было соответствующих курсов.

Скачать файлы

Наименование Файл Версия Размер
Двоичная арифметика
.epf 8,46Kb
0
.epf 8,46Kb Скачать

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

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

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

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

 

Бит А Бит Б Сумма
0 0 00
0 1 01
1 0 01
1 1 10

 

 

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

 

Бит переноса

предыдущего

сложения

Бит А Бит Б Сумма
0 0 0 00
0 0 1 01
0 1 0 01
0 1 1 10
1 0 0 01
1 0 1 10
1 1 0 10
1 1 1 11

 

 

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

 

  00010111  
+ 00011101 
= 00110100

 

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

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

 

 

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

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

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

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

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

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

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

 

 
 Upd 05.12.2022 (спасибо starik-2005):

 

Что получится, если мы попытаемся сложить два числа 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, при сложении чисел разных знаков возможное переполнение учитывать не нужно, оно чисто техническое и не играет роли. 

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

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

 

- 1
1 1

 

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

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)

 

 

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

 

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

 

 
 Некоторые из прочих моих публикаций 

 

Бит Байт Двоичный код Прямой Дополнительный арифметика сложение сдвиг процессор

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7460    4    SpaceOfMyHead    17    

56

[После] Новогодние задачи 2023

Математика и алгоритмы О жизни Бесплатно (free)

Не желаете ли очередную порцию интересных задач?

03.01.2023    2339    Alxby    20    

9

Если хочется ООП с наследованием и полиморфизмом

Математика и алгоритмы Языки и среды Платформа 1С v8.3 Абонемент ($m)

Объектно-ориентированное программирование (ООП), как методология или парадигма, в 1С отсутствует. И не похоже, чтобы в ближайшем будущем оно появилась. Однако со стороны сообщества не прекращаются попытки привнести в процесс разработки некоторые его элементы и подходы. Предлагаю вашему вниманию свой вариант эмуляции ООП. Основной упор в статье сделан на обеспечение наследования и полиморфизма (вызов методов, определенных в классах-потомках, из методов классов-предков и наоборот).

1 стартмани

21.07.2022    5052    1    Alxby    11    

10

По-настоящему свои макеты в отчетах СКД. Исследование процесса компоновки и генерация кода отчета

СКД Платформа 1С v8.3 Система компоновки данных Конфигурации 1cv8 Абонемент ($m)

Как скрестить формирование отчетных данных с помощью СКД и вывод в табличный документ с помощью Макет.ПолучитьОбласть(...) и ТабДок.Вывести(Секция)? А также сделать этот процесс простым и удобным? Об этом в статье ниже.

1 стартмани

22.03.2022    9614    Alxby    10    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Шаблоны автозамены для быстрого написания программного кода 1С и текстов запросов

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

Предлагаю вашему вниманию свой вариант файла шаблонов (*.st). Включены шаблоны для синтаксических конструкций, стандартных областей и директив компиляции, немодальных функций интерактивного ввода как с оповещениями, так и асинхронных. Добавлены шаблоны для упрощения написания текстов запросов. Учтены рекомендации стандартов разработки от 1С.

1 стартмани

11.03.2022    7734    65    Alxby    11    

27
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. kalyaka 1053 02.12.22 11:08 Сейчас в теме
Вот так можно эмулировать элементарные арифметические операции с помощью логических операций и сдвига
Не все так радужно :) Проблема в том, что мы живем в десятичной системе счисления, а расчеты производятся в двоичной и поэтому неизбежны ошибки округления. Именно поэтому в Excel или в Javascript следующее выражение 0.5-0.4 даст неожиданный результат: 0.09999999999999998.
2. Alxby 1136 02.12.22 12:36 Сейчас в теме
(1)Да, есть такая проблема. Но связана она с невозможностью точно представить двоичной системе дробные числа, записанные в десятичной системе. Точно так же, как и 1/3 в троичной представлена как 0.1, а в десятичной - 0.33333333.... Вдобавок часто дробные числа (double, float) хранятся в экспоненциальном формате, а значит не всегда можно сохранить результат, например, 10000000000000000-0.000000000000001. Если я не ошибаюсь в 1С таких проблем нет - все числа хранятся в "нормальном" виде - целая и дробная часть.
3. Alxby 1136 02.12.22 18:11 Сейчас в теме
(1)Ошибки при работе с дробями не всегда неизбежны. Проверил на Jav * ascript: 0.5-0.4 дает "неверный" результат, а 0.75-0.5 = 0.25 т.е. результат "верный". Здесь, видимо, дело вот в чем: основание десятичной системы - произведение простых множителей 2 и 5. Если в обычной дроби знаменатель раскладывается только на множители основания системы счисления, или их степени, то дробь точно представляется в этой системе, иначе - нет. Т.е. 1/2, 4/10, 7/25 будут точно представлены в десятичной системе, а 1/3, 3/7 и т.д. - только в виде бесконечной дроби. Аналогично 1/2, 3/4 в двоичной системе будут точно представлены, а 1/3 и 4/10 - нет. В первом примере 0.5=1/2 точно задается в двоичной системе, а 0.4=2/5 - нет. Поэтому и результат такой "неверный". А 0.75=3/4, 0.5=1/2 - оба числа "верно" будут заданы в двоичной системе и результат будет "верным". Кстати, существует двоично-десятичный код и микросхемы, поддерживающие операции с ним. Там проблем с конвертацией не будет, но арифметика в таком представлении гораздо сложнее.
5. starik-2005 3033 05.12.22 11:09 Сейчас в теме
(3)
Кстати, существует двоично-десятичный код и
А ассемблере почти всех процессоров, которые я видел, есть помимо всех этих АДД еще и ААД и т.д. http://av-assembler.ru/asm/afd/bcd.htm
6. Alxby 1136 05.12.22 12:14 Сейчас в теме
(5)Насколько я помню, при ассемблерных арифметических операциях необходимо дополнительно использовать команды специальной подготовки операндов и/или специальной обработки результата, что значительно замедляет и усложняет вычисления.
7. starik-2005 3033 05.12.22 12:19 Сейчас в теме
(6)
что значительно замедляет и усложняет вычисления
Ну одна команда ассемблера преобразует обычное число в 10-е дополненное, потом умножай/дели/вычитай и т.д. Вряд ли одна команда может тут серьезно что-то сильно замедлить и усложнить. Остальные команды - это просто варианты для дополненной 10-й арифметики. Ну и если нужно, то обратно преобразуй.
9. Alxby 1136 05.12.22 12:22 Сейчас в теме
(7)Нет, это надо делать после каждой операции
12. starik-2005 3033 05.12.22 12:38 Сейчас в теме
(9) После каждой операции (ну и перед делением - тоже) нужны команды коррекции, которые проверяют, нет ли в младших тетрадах значений за пределами десятки и всего такого. Просто мой пост был на тему того, что это не "и микросхемы, поддерживающие операции с ним", а большинство современных (и даже несовременных) процессоров. Т.е. эти команды есть в любом калькуляторе.
15. Alxby 1136 05.12.22 12:44 Сейчас в теме
(12)С этим согласен. Что не отменяет факта существования специализированных микросхем. А на заре существования компьютеров были экземпляры, работающие исключительно в BCD
4. starik-2005 3033 05.12.22 11:05 Сейчас в теме
Чета с умножением, имха, "проще" можно:
Функция MUL(А, Б)
  Если Б Тогда
    Возврат MUL( ПобитовоеИсключительноеИли( А , Б ), ПобитовыйСдвигВлево( ПобитовоеИ( А , Б ), 1 ) );
  Иначе
    Возврат А 
  КонецЕсли;
КонецФункции;
8. Alxby 1136 05.12.22 12:22 Сейчас в теме
(4)Да, выглядит это компактнее. Только в низко-низкоуровневом программировании не комильфо использовать рекурсию там, где можно обойтись без нее)). Наоборот, как правило, рекурсию стараются преобразовать в цикл.
10. Alxby 1136 05.12.22 12:24 Сейчас в теме
(4)Здесь точно нет ошибки? Сейчас нет возможности проверить, но как-то правильность этого примера вызывает сомнения...
11. starik-2005 3033 05.12.22 12:34 Сейчас в теме
(10) Проверял на С++ - работало исправно. Фактически это свернутый в рекурсию цикл "Пока Б Цикл".
13. Alxby 1136 05.12.22 12:41 Сейчас в теме
(11)Выглядит это не как умножение, а как сложение. Если в А накапливаются биты суммы, а в Б - биты переносов.
14. starik-2005 3033 05.12.22 12:41 Сейчас в теме
(13)
а как сложение
Возможно. Старый стал, могу что-то спутать )
16. Alxby 1136 05.12.22 13:41 Сейчас в теме
(14)Добавил Ваш вариант в статью. Спасибо!
17. sandr13 32 01.06.23 13:20 Сейчас в теме
Огромная благодарность автору. Прошиб до слёз от ностальгии. Жаль мало таких статей. Особая благодарность за картинки с транзисторами.
18. sandr13 32 01.06.23 13:21 Сейчас в теме
(17) Пойду что-нибудь спаяю из имеющихся в наличии транзисторов и резисторов.
20. Alxby 1136 01.06.23 19:04 Сейчас в теме
(18)... давненько не брал я в руки шашек паяльник с осциллографом... :)
19. Alxby 1136 01.06.23 19:02 Сейчас в теме
(17)Да и мне приятно было вспомнить! Вдруг эта тема еще кого-нибудь заинтересует. Основы забывать нельзя - все может в жизни пригодиться.
Оставьте свое сообщение