Побитовые операции "на пальцах"

02.08.19

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

Простой пример для понимания того, как это работает.

Введение

Начиная с версии платформы 8.3.11.2867 стал доступен ряд побитовых операций. Как это применимо в прикладной области, сложно сказать, но как это работает, понять можно. В этой публикации я не буду пересказывать теорию хранения данных в памяти, а лишь приведу тот минимум, который необходим для понимания публикации. 

Теория

Под каждое число ОС выделяет определенный участок в памяти. Его размер зависит от типа числа. Платформа 1С сама заботится о типах - это называется динамической типизацией. Но если открыть синтакс-помощник и найти там например функцию ПобитовоеИ, то в описании сказано, что в качестве параметра может быть указано число в диапазоне 0 – 2^32-1 (4.294.967.295), что соответствует типу unsigned long int. Максимальный размер такого числа будет 32 бита (4 байта). Каждый бит в памяти может быть представлен 1 или 0. Число начинает формироваться начиная с самого правого бита (00000000000000000000000000000001 - 1 с типом unsigned long int в двоичной системе).

Практика

В качестве практики реализуем функцию, которая будет преобразовывать число из десятичной системы в двоичную, используя побитовые операции. Идея такого алгоритма в следующем - нужно проверить каждый бит числа на наличие в нем 0 или 1. Из полученных таким образом чисел, можно составить представление исходного числа в двоичной системе. Другими словами, каждый бит числа типа unsigned long int нужно сравнить с 1. Таких битов в числе этого типа 32, то есть можно использовать цикл. Ранее я привел пример того, как выглядит 1 в двоичной системе. То есть если в цикле передвигать первый бит начиная с самого старшего, то получится, что за время цикла 1 "побывает" в каждом из битов. Это можно назвать маской. В виде таблицы можно представить вот так:

Номер итерации Десятичное представление (1*2^НомерИтерации) Двоичное представление
31 2,147,483,648 10000000000000000000000000000000
... ... ...
3 8 00000000000000000000000000001000
2 4 00000000000000000000000000000100
1 2 00000000000000000000000000000010
0 1 00000000000000000000000000000001

Теперь на каждой итерации можно "сравнивать" биты исходного числа с десятичным числом из средней колонки таблицы. В случае полного совпадения битов (1-1 или 0-0) результат должен быть также 1 или 0, в противном случае всегда 0. В полученном таким образом числе, текущий бит (номер итерации) нужно сдвинуть вправо на количество битов, равное номеру итерации.

Описанный алгоритм реализуется средствами языка платформы 1С следующим образом:

Result = "";
Size = 32;
Counter = Size - 1;
While Counter >= 0 Do
    // ПобитовыйСдвигВлево
	Mask = BitwiseShiftLeft(1, Counter);
    // ПобитовоеИ
	NumberAfterCompare = BitwiseAnd(Mask, LongToBinary);
    // ПобитовыйСдвигВправо
	OneOrZero = BitwiseShiftRight(NumberAfterCompare, Counter);
	Result = Result + String(OneOrZero);
EndDo;  
Message(Result);

Но, разработчики платформы сделали пару функций, которые облегчат решение данной задачи. В данном случае переменную OneOrZero можно получить следующим образом:

// ПроверитьПоБитовойМаске
OneOrZero = ?(CheckByBitMask(LongToBinary, Mask), 1, 0);

Но и это не все. В следующем примере даже нет необходимости вычислять маску:

// ПроверитьБит
OneOrZero = ?(CheckBit(IntToBinary, Counter), 1, 0);

Вместо заключения приведу еще один простой пример. Эта операция известна как swap. Кто не знает что это такое - обязательно запустите, будете удивлены.

a = BitwiseXor(a, b);
b = BitwiseXor(a, b);
a = BitwiseXor(a, b);

P.s. Есть еще несколько функций платформы для работы с битами. Краткое их описание на зазеркалье.

Побитовые операции двоичные данные bitwise operations binary data

См. также

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

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

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

1 стартмани

30.01.2024    1753    stopa85    12    

33

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

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

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

19.10.2023    4415    user1959478    50    

34

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

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

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

1 стартмани

09.06.2023    7458    4    SpaceOfMyHead    17    

56

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

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

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

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

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

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8834    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7801    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. CyberCerber 852 02.08.19 11:12 Сейчас в теме
Недавно писал генерацию QR, DataMatrix и других ШК на чистом 1С, поэтому с такими операциями повозился.
Понял, насколько 1С все же медленный. Чтобы добиться скорости генерации хотя бы 10 ШК в секунду, пришлось поизвращаться.
Например, операция BitwiseXor или ПобитовоеИсключительноеИли (Кстати, почему Исключительное, а не Исключающее? Странно...). Так вот, она используется в алгоритме очень часто для создания байтов коррекции. Оказалось самой дорогой частью кода, в итоге, т.к. вычисления идут в рамках байта, заранее загнал все варианты сумм в соответствие, брал результат оттуда, стало быстрее.
dctvghbdtn; nbeliaev; Blagin; acanta; +4 Ответить
2. nbeliaev 828 02.08.19 12:07 Сейчас в теме
(1) отличный пример применения данного функционала платформы
8. Xershi 1474 03.08.19 04:42 Сейчас в теме
(1) на джава скрипте 8к строк было кажись.
Все перевел?
11. CyberCerber 852 03.08.19 08:54 Сейчас в теме
(8) Хм, не знаю, что там на 8К... У меня 700 - 800 где-то. Но я не переводил с другого языка, с нуля писал.
3. for_sale 971 02.08.19 12:56 Сейчас в теме
Ничего не понял, но очень интересно)
WellMaster; yuran2000; FesenkoA; Jeka44; +4 Ответить
4. lic_avenger 10 02.08.19 16:40 Сейчас в теме
Кто в теме. Где, когда, и т.д. и т.п это применяется? и главное для чего? можете объяснить?
12. CyberCerber 852 03.08.19 08:57 Сейчас в теме
(4) Ну, функционал необычный, в создании печатной формы, наверное, не поможет... :-)
Я применял для генерации различных низкоуровневых вещей на чистом 1С: штрихкодов, ключей шифрования, файлов, например, картинок.
lic_avenger; +1 Ответить
14. lic_avenger 10 05.08.19 16:45 Сейчас в теме
(12) Спасибо! Теперь понятно (штрихкод, ключ,прочее)
16. eruil 09.02.22 17:57 Сейчас в теме
(4) операции с битами лежат в основе кодинга (странно, что 1С только сейчас опомнились). К примеру, позволяет в одном числе хранить множество состояний - см второй пример https://wonderland.v8.1c.ru/blog/rasshirenie-funktsionalnosti-raboty-s-dvoichnymi-dannymi
5. ltfriend 954 02.08.19 23:11 Сейчас в теме
А почему комментарии а коде на русском?
9. nbeliaev 828 03.08.19 07:40 Сейчас в теме
(5) это названия функций на русском как их можно найти в синтакс-помощнике.
6. bulpi 215 02.08.19 23:13 Сейчас в теме
То ли я тупой, то ли автор объясняет плохо. Непонятно ни фига.
for_sale; +1 Ответить
13. FesenkoA 57 05.08.19 10:21 Сейчас в теме
(6) не хочу вас обидеть, но вы упускаете третий вариант
Ложь = истина и ложь;
Ложь = ложь и истина;
Ложь = ложь и ложь;
7. bulpi 215 02.08.19 23:22 Сейчас в теме
И я запустил "swap" и совершенно не удивлен. Все очевидно.
10. nbeliaev 828 03.08.19 07:42 Сейчас в теме
(7) а Вы часто хотите удивиться, делая знакомые вещи?
15. eruil 09.02.22 17:55 Сейчас в теме
А на 8.2 с битами работать 1С не умеет ?
Оставьте свое сообщение