gifts2017

Битовые операции

Опубликовал Валерий (scientes) в раздел Программирование - Практика программирования

Пример того, как можно вызывать битовые операции из 1С
Занимаясь программой для поиска решений головоломки Bedlam Cube, я задался вопросом, а можно ли в 1С реализовать битовые операции. Дело в том, что кубик, который надо собрать, имеет размеры 4х4х4. А значит его можно описать с помощью 64-х разрядного числа, в котором каждый бит соответствует ячейке (клетке) головоломки. В 1С числа представляются в виде строк и , как следствие, операций над битами нет. Но побитовые операции есть в Transaq-SQL (& - побитовое И, | - побитовое ИЛИ, ^ -  побитовое исключающее ИЛИ). Среди типов данных, которые входят в стандарт языка Transaq-SQL присутствует bigint, которое имеет длину 8 байт, что и соответствует 64-х разрядному числу. Сначала я создал хранимые процедуры, с помощью которых выполняются побитовые операции. Ниже приведен пример одной из них.

CREATE PROCEDURE [dbo].[BitOR]

-- Add the parameters for the stored procedure here
@BigInt1 bigint,
@BigInt2 bigint
AS
BEGIN
 SET NOCOUNT ON;
 SELECT @BigInt1 | @BigInt2
END

Аналогично можно реализовать две оставшиеся операции. Теперь покажем как организовать вызов данных процедур из 1С. Для этого нам потребуется подключение к SQL серверу.
Функция глSQLПодключение() Экспорт
SQLConnect = Новый COMОбъект("ADODB.Connection"); 
ConnectionString = "driver={SQL Server}; server=<Имя сервера>; uid=<Имя пользователя>; pwd=*******; DataBase=<Имя базы> ";
SQLConnect.ConnectionTimeOut =600;SQLConnect.CursorLocation = 3;
попытка
SQLConnect.Open(ConnectionString);
исключение
SQLConnect="";
Предупреждение("Невозможно установить соединение");
возврат Неопределено;
конецпопытки;
возврат SQLConnect;
КонецФункции
Приведенная функция в случае успешного завершения возвращает com-объект, который позволяет выполнять команды на SQL сервере. Используя созданное подключение, мы можем вызвать хранимую процедуру. Ниже пример того, как это сделать из 1С.
Функция BitOr(вхЧсл1,вхЧсл2,вхSQLConnect)
CmdSQL = Новый COMОбъект("ADODB.Command")    ;
CmdSQL.ActiveConnection = вхSQLConnect       ;   
CmdSQL.CommandText = "EXEC [dbo].[BitOr] "+Формат(вхЧсл1,"ЧН=0; ЧГ=0")+","+Формат(вхЧсл2,"ЧН=0; ЧГ=0");
rs=CmdSQL.Execute();
rs.MoveFirst();
возврат rs.Fields(0).Value;
КонецФункции
Теперь поговорим о том, как получить текущее состояние кубика. В 1С реализованы длинное умножение и сложение, а длина данных, с которыми можно оперировать, определяется исключительно размером доступной памяти. Поэтому получить массив, в котором хранятся значения степеней двойки для значений показателя от 0 до 63, труда не составляет. Далее каждой  точке с координатами x,y и z  мы можем сопоставить число из диапазона 0...63. Это число рассчитывается по формуле z+4*(y+4*x). После этого, чтобы получить состояние,описывающее наш кубик, мы должны для каждой заполненной точки вычислить ее положение в одномерном массиве, найти значение двойки в данной степени и полученные числа сложить. Все просто и понятно. Но тип данных bigint хранит данные в диапазоне (-2^63) до (2^63-1), а значит при попытке передать в хранимую процедуру число 2^63 мы получим ошибку. Нам надо понять какому значению соответствует двоичная запись, которая содержит 0 во всех разрядах, кроме самого старшего. Для этого надо найти информацию о представлении в памяти целых отрицательных чисел. Это не сложно. Алгоритм следующий, надо взять двоичную запись положительного числа, инвертировать ее, то есть 0 заменить на 1, а 1 на 0, затем к получившемуся числу прибавить 1. Используя полученные сведения, найдем представление для (-1):
  1. Двоичная запись 1 - 0x000...001
  2. Инвертируем 0x111...110
  3. Прибавляем 1, получаем 0x111...111
Вспоминаем, что двоичная запись для (2^63 -1) это 0x011...111 ( единица во всех разрядах кроме старшего). Ну и последний шаг, вычтем из двоичного представления для (-1) двоичное представление для (2^63 -1), получим 0x100...000. Таким образом, когда нам надо заполнить самый старший бит в двоичном представлении нашего куба, мы должны к числу, описывающему текущее состояние, прибавить (-2^63). Что я и сделал. И это все заработало !
Поиск решения заключается в переборе всех возможных вариантов исходных элементов. Для этого я предварительно подготовил таблицу состояний, в которой  для каждой фигуры и каждого  положения фигуры вычислил ее характеристику, как это описано выше. Затем в процедуре поиска, когда мне нужно было проверить можно ли разместить фигуру в кубике, я вычислял логическое И между текущим состоянием и характеристикой фигуры и если оно равнялось нулю, то фигуру можно было разместить. Поставить фигуру - вычислить логическое ИЛИ между текущим состоянием и характеристикой фигуры, снять фигуру - вычислить логическое ИСКЛЮЧАЮЩЕЕ ИЛИ  между текущим состоянием и характеристикой фигуры. Разумеется, изложенную методику я реализовал, как дополнительную к более простой, когда состояние кубика описывалось трехмерным массивом.
Ну и ответ на вопрос, зачем это надо. Человеческий мозг содержит около 86 млрд. нейронов, но не это количество делает его поистине уникальным. Значительно важнее связи между нейронами, а вот здесь количество сочетаний становится просто астрономическим. Возможно, прочитав эту статью, у вас сложится неожиданная цепочка, которая впоследствии приведет к решению задачи, весьма далекой от изложенной. 




См. также

Подписаться Добавить вознаграждение

Комментарии

1. viollan (viollan) 30.07.14 11:47
Прошу прощения, но заголовок статьи не соответствует содержанию. Вы выполняете побитовые операции не на 1С, а на SQL. С таким успехом можно выполнить эти действия используя .Net, ВК и пр.
2. Валерий (scientes) 30.07.14 12:36
Благодарю за замечание, внес исправления в анонс статьи.
3. Александр (kg_am) 01.08.14 12:42
Что-то мне подсказывает, что вызов CmdSQL.Execute() будет происходить по-любому на порядок дольше, чем если средствами языка 1С перевести числа в двоичную систему и сделать всё, что нужно.
4. Валерий (scientes) 04.08.14 14:21
Вы правы, решение с обращением к SQL серверу увеличивает время расчета, и чем больше перебирается вариантов, тем больше это различие. Я и не говорю, что предложенный способ лучше. Он рабочий, это верно.
5. Александр (kg_am) 05.08.14 20:07
У меня получилась такая функция побитового "или":

Функция BitOr(вхЧсл1, вхЧсл2)
	ОстатокЧ1 = вхЧсл1;
	ОстатокЧ2 = вхЧсл2;
	Множитель = 1;
	Результат = 0;
	Пока ОстатокЧ1 <> 0 и ОстатокЧ2 <> 0 Цикл
		Результат = Результат + Макс(ОстатокЧ1 % 2, ОстатокЧ2 % 2) * Множитель;
		ОстатокЧ1 = Цел(ОстатокЧ1 / 2);
		ОстатокЧ2 = Цел(ОстатокЧ2 / 2);
		Множитель = Множитель * 2;
	КонецЦикла;
	Возврат Результат + (ОстатокЧ1 + ОстатокЧ2) * Множитель;
КонецФункции
...Показать Скрыть


Дёшево и сердито. Главное - быстро.
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа