Простая и быстрая эмуляция операций с битовыми строками
22.06.2016
Простая и быстрая эмуляция операций с битовыми строками
Битовые строки могли бы упростить реализацию некоторых алгоритмов на языке платформы «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; ЧЦ=" + Разрядность;
Текст публикации
Простая и быстрая эмуляция операций с битовыми строками
Битовые строки могли бы упростить реализацию некоторых алгоритмов на языке платформы «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; ЧЦ=" + Разрядность;
Текст публикации
купить, программ, 1С, 1, С, в, Егорьевске, Московской, бухгалтерия, предприятие, продукт, 2, 3, 8, 7, 10, 11, 5, 0, торговля, склад, зарплата, кадры, управление, персонал, настроить, обучение, на, курсы, компьютерный, центр, ООО, ИНТЕХ, учет, производство, ERP, УПП, УТ, ЗУП, упрощенка, документооборот, розница, небольшая, фирма, деньги, скачать, сопровождение, внедрить, обновить, обучить, франчайзи, организация, поддержка, сертифицированный, аттестованный, компьютер, Егорьевск, Москва, область, Воскресенск, Шатура, Ликино, Коломна, Рошаль, Бронницы, Шувое, Куровское, Луховицы, ЭЦП, отчетность, ИТС, электронный, архив, автоматизация, оперативный, техподдержка, телефон, Интернет, аренда, автосервис, магазин, бухфон, горячая, линия, битрикс, версия, лицензия, линк, релиз, сайт, фреш, ЦСО, ЭДО, яндекс, карта. купить, программ, 1С, 1, С, в, Егорьевске, Московской, бухгалтерия, предприятие, продукт, 2, 3, 8, 7, 10, 11, 5, 0, торговля, склад, зарплата, кадры, управление, персонал, настроить, обучение, на, курсы, компьютерный, центр, ООО, ИНТЕХ, учет, производство, ERP, УПП, УТ, ЗУП, упрощенка, документооборот, розница, небольшая, фирма, деньги, скачать, сопровождение, внедрить, обновить, обучить, франчайзи, организация, поддержка, сертифицированный, аттестованный, компьютер, Егорьевск, Москва, область, Воскресенск, Шатура, Ликино, Коломна, Рошаль, Бронницы, Шувое, Куровское, Луховицы, ЭЦП, отчетность, ИТС, электронный, архив, автоматизация, оперативный, техподдержка, телефон, Интернет, аренда, автосервис, магазин, бухфон, горячая, линия, битрикс, версия, лицензия, линк, релиз, сайт, фреш, ЦСО, ЭДО, яндекс, карта,
Обновление 1С, управленческий учет, бухгалтерский учет
Наша компания также занимается разработкой собственных программных продуктов на платформе «1С:Предприятие 8».
В нашей компании работают сертифицированные фирмой «1С» специалисты, которые постоянно совершенствуют свои знания и навыки. Они помогут качественно и оперативно решить задачи по автоматизации управления и учета на вашем предприятии.
Наша компания опирается в своей работе на знание и повседневное применение стандартов качества, проектных методов в управлении, процессного подхода в организации нашей деятельности.
Компания хорошо организована, в ней четко распределены обязанности, процедуры, соблюдается технология работы, имеются оперативные инструкции, документированные и известные всему персоналу, существуют отработанные процедуры контроля выполняемых работ и, конечно, профессиональный и хорошо обученный персонал, способный качественно выполнять свою работу.
