Простая и быстрая эмуляция операций с битовыми строками

22.06.16

Разработка - Механизмы платформы 1С

Битовые строки могли бы упростить реализацию некоторых алгоритмов на языке платформы «1С: Предприятие 8». Но пока в платформе операций с битовыми строками нет.  В то же время уже сделанные попытки смоделировать эти операции преобразованиями над числами опираются на циклы обработки отдельных битов, что плохо сказывается на скорости их работы. Предлагается новое простое решение, основанное на представлении битовых строк строками символов «0» и «1». Приводится примеры кода выполнения основных логических операций AND, OR, XOR, NO без использования циклов.
В качестве прикладной задачи рассмотрено получение последовательных значений кода Грэя, который можно использовать для ускорения перебора вариантов.

В статье «Расчет SHA-1 хеша средствами 1С. Битовые операции в 1С или урок двоичной математики» приведен набор функций, позволяющий работать с числами как с битовыми строками. В основе всех приведенных там функций лежат циклы побитовой обработки.

Альтернативным способом представления битовых строк как чисел является их представление символьными строками. Хранение битовых строк как символьных строк из «0» и «1» хоть и отнимает в 8 (16) раз больше памяти, но дает возможность избавиться от циклов при выполнении логических операций над строками.

1. Функция "ИЛИ"

Например, операция логического «или» (or, дизъюнкции) входных битовых строк Х и У может быть выполнена так:

СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "1")

где форматная строка предполагает заданную разрядность, отсутствие делений на группы цифр, дополнение ведущими нулями и представление нуля цепочкой нулей, длина которой равна разрядности битовой строки. То есть:

Нули = СтрЗаменить(Формат(1, "ЧВН=; ЧГ=0; ЧЦ=" + Разрядность), "1", "0");
ФорматнаяСтрока = "ЧН=" + Нули + "; ЧВН=; ЧГ=0; ЧЦ=" + Разрядность;

Например, в соответствии с правилами выполнения логической операции «или» для исходных строк

Х = «0101»;

У = «0011»

будет получен результат:

Ф = «0111».

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

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

Из-за особенностей работы функции «формат» длина битовых (символьных) строк, обрабатываемых таким образом, ограничена 309 битами (символами).

2. Функция "XOR"

Так же просто выглядит операция логическое «исключающее или» (xor, неравнозначность):

СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "0")

Для примера можно взять две 64-х разрядных строки:

Х = «1000110100011101010111111010101000000011111101000111110000000111»;

У = «1000110100011101010111111110101000000011111101000111110000000111»

и получить следующий правильный результат:

Ф = «0000000000000000000000000100000000000000000000000000000000000000».

3. Функция "НЕ"

Еще проще выглядит операция логического отрицания «не» (no, отрицание):

СтрЗаменить(СтрЗаменить(СтрЗаменить(Х, "1", "_"), "0", "1"), "_", 0)

4. Функция "И"

Несколько сложнее выглядит операция логического «и» (and, конъюнкция):

СтрЗаменить(СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "1", "0"), "2", "1")

5. Замечания и уточнения 

Хотя основной сценарий использования операций над битовыми строками предполагает, что они имеют равную длину, соответствующую заранее выбранной фиксированной разрядности, функции работают и со строками разной длины, если она меньше заданной разрядности. При этом строки выравниваются ПО ПРАВОМУ КРАЮ. Конечно, при желании это можно изменить, чуть усложнив код.

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

Проверка быстродействия приведенного приема показывает выигрыш примерно в 15 раз по сравнению с функциями, приведенными в статье "Битовые операции в 1С или урок двоичной математики ".

Немаленьким бонусом является возможность подсчета числа единиц (нулей) в строке с использованием встроенной функции языка СтрЧислоВхождений(БитоваяСтрока, «1»), что для чисел требует оптимизации даже на уровне ассемблера [Обстоятельно о подсчёте единичных битов ].

Функция Сред позволяет легко проверять значения отдельных битов, могут пригодиться и другие строковые функции.

При большом желании таким образом можно реализовать и арифметические функции. Правда, в этом случае младшие разряды чисел удобнее располагать слева.

Вот, например, так выполняется операция инкремента (младший разряд слева):

Яма = Найти(Х, "0");
Х = Лев(Нули, Яма - 1) + "1" + Сред(Х, Яма + 1)

 

6. Практическое применение: код Грэя

В качестве примера применения данного подхода предлагается реализация функции, получающей следующее значение двоичного кода Грэя [ссылка]. Этот код отличается тем, что каждое следующее значение кода отличается от предыдущего только в одном разряде, при этом в N разрядах содержится ровно 2^N значений. Данный код удобно использовать при решении задач перебора, поскольку на каждый итерации становится возможным не формировать тестовый набор заново, а получать его из предыдущего включением или исключением всего одного элемента.

Правило получения следующего значения таково [http://rsdn.ru/article/alg/gray.xml]: если число единиц в текущем значении кода четно, то инвертируется первый бит текущего значения кода, в противном случае инвертируется бит, следующий за первой единицей.

В итоге получается следующая функция:

Функция СледующийПоГрэю(Код, Позиция = 0)
            Нули = СтрЗаменить(Код, "1", "0");
            ФорматнаяСтрока = "ЧН=" + Нули + "; ЧВН=; ЧГ=0; ЧЦ=" + СтрДлина(Код);
            Позиция = ?(СтрЧислоВхождений(Код, "1") % 2 = 0, 1, Найти(Код, "1") + 1);
            Маска = "1" + Сред(Нули, Позиция + 1);
            Возврат СтрЗаменить(Формат(Число(Код) + Число(Маска), ФорматнаяСтрока), "2", "0");
КонецФункции

При последовательности вызовов с начальным значением «0000» функция производит следующую последовательность значений кода:

1000

1100

0100

0110

1110

1010

0010

0011

1011

1111

0111

0101

1101

1001

0001

0000

и так далее.

Выводы

Конечно, генерацией кода Грэя применение битовых строк не исчерпывается.

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

Кроме того, можно надеяться, что с появлением нового простого инструмента круг решаемых этим инструментом задач также расширится.

Приложение

Далее приведен весь код в виде набора функций, необходимых для обработки "битовых строк":

Перем Нули, Единицы, ФорматнаяСтрока;

Функция Неравнозначность(Х, У)
	Возврат СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "0")	
КонецФункции

Функция Дизъюнкция(Х, У)
	Возврат СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока), "2", "1")
КонецФункции

Функция Конъюнкция(Х, У)
	Возврат СтрЗаменить(СтрЗаменить(Формат(Число(Х) + Число(У), ФорматнаяСтрока)
, "1", "0"), "2", "1")	
КонецФункции

Функция Отрицание(Х)
	Возврат Формат(Число(Единицы) - Число(Х), ФорматнаяСтрока)	
КонецФункции

Функция Сдвиг(Х, У)
	Возврат Формат(Число(Х), ФорматнаяСтрока + "; ЧС=" + У)	          
КонецФункции

Функция _Отрицание(Х)
	Возврат СтрЗаменить(СтрЗаменить(СтрЗаменить(Х, "1", "_"), "0", "1"), "_", 0)	
КонецФункции

Функция Инкремент(Х)
	Яма = Найти(Х, "0");
	Возврат ?(Яма = 0, Х, Лев(Нули, Яма - 1) + "1" + Сред(Х, Яма + 1))	
КонецФункции

Функция Декремент(Х)
	Пик = Найти(Х, "1");
	Возврат ?(Пик = 0, Х, Лев(Единицы, Пик - 1) + "0" + Сред(Х, Пик + 1))	
КонецФункции

Функция СледующийПоГрэю(Код, Место = 0)
	Место = ?(СтрЧислоВхождений(Код, "1") % 2, Найти(Код, "1") + 1, 1);
	Маска = "1" + Сред(Нули, Место + 1);
	Возврат СтрЗаменить(Формат(Число(Код) + Число(Маска), ФорматнаяСтрока), "2", "0");	
КонецФункции

Разрядность = Мин(Разрядность, 309);
Нули = СтрЗаменить(Формат(1, "ЧВН=; ЧГ=0; ЧЦ=" + Разрядность), "1", "0");
Единицы = СтрЗаменить(Нули, "0", "1");
ФорматнаяСтрока = "ЧН=" + Нули + "; ЧВН=; ЧГ=0; ЧЦ=" + Разрядность;

битовые строки логические операции

См. также

Поинтегрируем: сервисы интеграции – новый стандарт или просто коннектор?

Обмен между базами 1C Администрирование СУБД Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

В платформе 8.3.17 появился замечательный механизм «Сервисы интеграции». Многие считают, что это просто коннектор 1С:Шины. Так ли это?

11.03.2024    3600    dsdred    48    

66

Как готовить и есть массивы

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

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

24.01.2024    5037    YA_418728146    25    

62

Планы обмена VS История данных

Обмен между базами 1C Механизмы платформы 1С Платформа 1С v8.3 Бесплатно (free)

Вы все еще регистрируете изменения только на Планах обмена и Регистрах сведений?

11.12.2023    6165    dsdred    36    

110

1С-ная магия

Механизмы платформы 1С Бесплатно (free)

Язык программирования 1С содержит много нюансов и особенностей, которые могут приводить к неожиданным для разработчика результатам. Сталкиваясь с ними, программист начинает лучше понимать логику платформы, а значит, быстрее выявлять ошибки и видеть потенциальные узкие места своего кода там, где позже можно было бы ещё долго медитировать с отладчиком в поисках источника проблемы. Мы рассмотрим разные примеры поведения кода 1С. Разберём результаты выполнения и ответим на вопросы «Почему?», «Как же так?» и «Зачем нам это знать?». 

06.10.2023    18202    SeiOkami    46    

116

Дефрагментация и реиндексация после перехода на платформу 8.3.22

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

Начиная с версии платформы 8.3.22 1С снимает стандартные блокировки БД на уровне страниц. Делаем рабочий скрипт, как раньше.

14.09.2023    11770    human_new    27    

72

Валидация JSON через XDTO (включая массивы)

WEB-интеграция Универсальные функции Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

При работе с интеграциями рано или поздно придется столкнуться с получением JSON файлов. И, конечно же, жизнь заставит проверять файлы перед тем, как записывать данные в БД.

28.08.2023    8561    YA_418728146    6    

139

Внешние компоненты Native API на языке Rust - Просто!

Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Внешние компоненты для 1С можно разработывать очень просто, пользуясь всеми преимуществами языка Rust - от безопасности и кроссплатформенности до удобного менеджера библиотек.

20.08.2023    6201    sebekerga    54    

93

Все скопируем и вставим! (Буфер обмена в 1С 8.3.24)

Механизмы платформы 1С Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Рассмотрим новую возможность 8.3.24 и как её можно эффективно использовать

27.06.2023    15535    SeiOkami    31    

103
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Yashazz 4707 22.06.16 13:38 Сейчас в теме
Да, иногда не хватает. Хотя тут обещали в https://wonderland.v8.1c.ru/blog/novye-instrumenty-dlya-raboty-s-dvoichnymi-dannymi-obespechivayut-kak-posledovatelnyy-dostup-k-danny/ некоторые "побайтовые операции", но не сейчас и вообще пока неясно, как реализуют...
2. ildarovich 7846 22.06.16 13:52 Сейчас в теме
(1) Yashazz, да, я в курсе этих планов, поэтому и написал в анонсе "пока нет". Но мне показалось, что 1С это делает в основном для задач интеграции, сопряжения с оборудованием и тому подобное, а не для алгоритмических задач, но посмотрим.
Идея была на поверхности - жалко было проходить мимо.
8. DrAku1a 1678 27.06.16 02:55 Сейчас в теме
(1) Жду с нетерпением - когда 1С это реализует. Нормальных методов разбора multipart-HTTP запроса в 1С не хватает. У меня есть решение на BASE64-строках и разделением файлов, но оно - не самое эффективное.
(0) Автору статьи - очередной респект (+++).
3. premierex 204 25.06.16 13:17 Сейчас в теме
(0) а всё же, если реализовать алгоритм расчета SHA-1 с помощью Вашего метода, какой прирост в скорости выполнения он даст. Не тестировали?
4. premierex 204 25.06.16 13:31 Сейчас в теме
(0) И ещё в примере не указано, каким значением инициализируется переменная "Разрядность".
5. premierex 204 25.06.16 13:39 Сейчас в теме
(0) Функция Сдвиг(4, -2) при разрядности 8 выдает вот такой результат: 00000400. На битовую строку не похоже как-то...
6. premierex 204 25.06.16 14:08 Сейчас в теме
(0) Функция Дизъюнкция(4, 2) возвращает результат 00000006, тоже на битовую строку не похоже.
Поторопился плюс поставить или не понял чего-то?
7. premierex 204 25.06.16 14:20 Сейчас в теме
(0) Понял, кажется. На вход функций надо передать именно битовую строку. Тогда всё верно отрабатывает. А если я оперирую числами и хочу увидеть результат выполнения предложенных Вами функций, следует преобразовать операнды в битовые строки и обратные манипуляции проделать с результатом. Насколько я знаю, при таком преобразовании без циклов не обойтись. А так - решение интересное.
9. ИНТЕГРА 25 28.06.16 16:46 Сейчас в теме
Когда попадаются подобные статьи, у меня всегда возникает вопрос - на каких проектах применялись такие методы? Интересно было бы послушать.
Andreeei; so-quest; nbeliaev; +3 Ответить
10. aspirator23 339 02.07.16 15:03 Сейчас в теме
(9) ИНТЕГРА, на ваших будущих.
11. newold2 124 04.08.16 08:59 Сейчас в теме
Перевод строки в двоичную и обратно описан https://infostart.ru/public/274498/ (частный случай применения функции Стр_Перекодировка()).
12. v3rter 09.08.16 10:38 Сейчас в теме
Таки пообещали в 8.3.10 http://infostart.ru/journal/news/mir-1s/platformy-1s-predpriyatie-8-3-10-budet-luchshe-rabotat-s-dvoichnymi-dannymi%e2%80%94541161/

05.08.2016
... вы сможете выполнять прямое и обратное преобразование двоичных данных в обычную строку, строку формата Base64 и строку формата BinHex. Кроме этого сами двоичные данные вы можете преобразовать в форматы Base64, BinHex и обратно.

Аналогичные преобразования поддерживаются и для типа БуферДвоичныхДанных. Кроме этого буфер двоичных данных вы можете преобразовывать в двоичные данные и обратно.
...
Эффективное копирование с помощью чтения и записи данных.
Побитовые логические операции с буфером двоичных данных.
Получение числа из шестнадцатеричных и двоичных литералов.
13. ildarovich 7846 09.08.16 11:01 Сейчас в теме
(12) v3rter, да, видел эту заметку. Но там все же акцент делается на задачах интеграции, а не на алгоритмах, где могут понадобиться битовые строки.
С другой стороны, большого количества алгоритмических задач, которые могли бы показать возможности применения битовых строк (кроме уже приведенных задач с кодами), я пока не нашел.
Думал в направлении генетических алгоритмов, но пока безрезультатно.
Возможно, со временем, что-нибудь и найдется.
А новые возможности 8.3.10 очень интересны: открывают простор для творчества в области "безцикловых" преобразований данных в 1С.
Оставьте свое сообщение