Извлечение битов с одним умножением

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

Нам дано 64-разрядное целое число без знака, и нас интересуют следующие биты:

1.......2.......3.......4.......5.......6.......7.......8.......

В частности, мы хотели бы переместить их в верхние восемь позиций, вот так:

12345678........................................................

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

Решение было замаскировать нежелательные биты, и умножить результат на 0x2040810204081. Это, как оказывается, делает свое дело.

Насколько общий этот метод? Можно ли использовать эту технику для извлечения какого-либо подмножества битов? Если нет, то как выяснить, работает ли метод для определенного набора битов?

Наконец, как можно найти (a?) Правильный множитель для извлечения заданных битов?

Очень интересный вопрос и хитрый трюк.

Давайте посмотрим на простой пример манипулирования одним байтом. Использование 8-битного без знака для простоты. Представь, что твой номер есть xxaxxbxxи ты хочешь ab000000.

Решение состояло из двух этапов: немного маскировки с последующим умножением. Битовая маска - это простая операция И, которая превращает неинтересные биты в нули. В приведенном выше случае, ваша маска будет 00100100и результат 00a00b00.

Теперь самое сложное: превратить это в ab.......

Умножение - это набор операций сдвига и сложения. Ключ должен позволить переполнению «сдвинуть» ненужные нам биты и поместить нужные нам в нужное место.

Умножение на 4 ( 00000100) сместит все, что осталось, на 2 и приведет вас к a00b0000. Чтобы заставить bдвигаться вверх, нам нужно умножить на 1 (чтобы держать a в нужном месте) + 4 (чтобы переместить b вверх). Эта сумма равна 5, и в сочетании с предыдущими 4 мы получаем магическое число 20 или 00010100. Оригинал был 00a00b00после маскировки; умножение дает:

000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......

При таком подходе вы можете расширить до больших чисел и больше битов.

Один из заданных вами вопросов был: «Можно ли это сделать с любым количеством бит?» Я думаю, что ответ «нет», если вы не разрешаете несколько операций маскирования или несколько умножений. Проблема в проблеме «столкновений» - например, «заблудившийся б» в задаче выше. Представьте, что нам нужно сделать это с таким числом, как xaxxbxxcx. Следуя более раннему подходу, вы можете подумать, что нам нужно {x 2, x {1 + 4 + 16}} = x 42 (оооо - ответ на все вопросы!). Результат:

00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......

Как видите, он все еще работает, но «только что». Ключевым моментом здесь является то, что между битами, которые мы хотим, есть «достаточно места», чтобы мы могли все сжать. Я не мог добавить четвертый бит d сразу после c, потому что я получал случаи, когда я получал c + d, биты могли нести, ...

Поэтому без формального доказательства я бы ответил на более интересные части вашего вопроса следующим образом: «Нет, это не будет работать для любого количества бит. Чтобы извлечь N бит, вам нужно (N-1) пробелы между битами, которые вы хотите извлекать или иметь дополнительные шаги умножения маски. "

Единственное исключение, которое я могу придумать для правила «должны иметь (N-1) нули между битами», заключается в следующем: если вы хотите извлечь два бита, смежных друг с другом в оригинале, и хотите сохранить их в тот же порядок, тогда вы все еще можете сделать это. А для правила (N-1) они считаются двумя битами.

Есть еще одна идея, вдохновленная ответом @Ternary ниже (см. Мой комментарий там). Для каждого интересного бита вам нужно только столько нулей справа от него, сколько вам нужно места для битов, которые должны идти туда. Но также нужно столько же битов слева, сколько и битов результата слева. Таким образом, если бит b оказывается в позиции m из n, то он должен иметь нули m-1 слева и нули nm справа. Особенно, когда биты не находятся в том же порядке в исходном номере, как они будут после переупорядочения, это является важным улучшением к первоначальным критериям. Это означает, например, что 16-битное слово

a...e.b...d..c..

Может быть сдвинут в

abcde...........

хотя между e и b есть только один пробел, два между d и c, три между остальными. Что случилось с N-1? В этом случае a...eстановится «один блок» - они умножаются на 1, чтобы оказаться в нужном месте, и поэтому «мы получили е бесплатно». То же самое верно для b и d (b нужно три пробела справа, d нужно те же три слева). Поэтому, когда мы вычисляем магическое число, мы обнаруживаем, что есть дубликаты:

a: << 0  ( x 1    )
b: << 5  ( x 32   )
c: << 11 ( x 2048 )
d: << 5  ( x 32   )  !! duplicate
e: << 0  ( x 1    )  !! duplicate

Понятно, что если вы хотите, чтобы эти числа были в другом порядке, вам пришлось бы расположить их дальше. Мы можем переформулировать (N-1)правило: «Оно всегда будет работать, если между битами будет не менее (N-1) пробелов, или, если известен порядок битов в конечном результате, то если бит b окажется в позиции m n, он должен иметь нули m-1 слева и нули nm справа ".

@Ternary указал, что это правило не совсем работает, так как может быть переход от битов, добавляющих «только справа от целевой области», а именно, когда все искомые биты являются единицами. Продолжая пример, который я привел выше, с пятью плотно упакованными битами в 16-битном слове: если мы начнем с

a...e.b...d..c..

Для простоты я назову битовые позиции ABCDEFGHIJKLMNOP

Математика, которую мы собирались сделать, была

ABCDEFGHIJKLMNOP

a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00

До сих пор мы думали, что что-либо ниже abcde(позиции ABCDE) не будет иметь значения, но на самом деле, как указывало @Ternary, если b=1, c=1, d=1тогда (b+c)в позиции Gбудет немного переходить в позицию F, что означает, что (d+1)в позиции Fбудет немного переходить E- и наша результат испорчен. Обратите внимание, что пробел справа от наименее значимого бита, представляющего интерес ( cв этом примере), не имеет значения, так как умножение приведет к заполнению нулями от любого младшего значащего бита.

Поэтому нам нужно изменить наше правило (m-1) / (nm). Если имеется более одного бита, который имеет «точно (нм) неиспользуемые биты справа (не считая последний бит в шаблоне -« с »в примере выше), то нам нужно усилить правило - и мы должны делать это итеративно!

Мы должны смотреть не только на число битов, которые соответствуют критерию (нм), но также и на те, которые имеют (n-m + 1) и т. Д. Давайте назовем их число Q0 (точно n-mследующим битом), Q1 ( n-m + 1), до Q (N-1) (n-1). Тогда мы рискуем нести, если

Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
... 

Если вы посмотрите на это, вы увидите, что если вы напишите простое математическое выражение

W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)

и в результате W > 2 * Nвы должны увеличить критерий RHS на один бит до (n-m+1). На данный момент, операция безопасна, пока W < 4; если это не сработает, увеличьте критерий еще раз и т. д.

Я думаю, что следуя вышесказанному, вы получите длинный путь к вашему ответу ...

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

"Существует несколько 64-битных констант 'mask' и 'multiplicand', так что для всех 64-битных битовых векторов x в выражении y = (x & mask) * multiplicand мы имеем, что y.63 == x.63 , y.62 == x.55, y.61 == x.47 и т. д. "

Если это предложение на самом деле является теоремой, то верно, что некоторые значения констант «маска» и «умножение» удовлетворяют этому свойству. Итак, давайте сформулируем это в терминах чего-то, что может понять доказатель теоремы, а именно ввода SMT-LIB 2:

(set-logic BV)

(declare-const mask         (_ BitVec 64))
(declare-const multiplicand (_ BitVec 64))

(assert
  (forall ((x (_ BitVec 64)))
    (let ((y (bvmul (bvand mask x) multiplicand)))
      (and
        (= ((_ extract 63 63) x) ((_ extract 63 63) y))
        (= ((_ extract 55 55) x) ((_ extract 62 62) y))
        (= ((_ extract 47 47) x) ((_ extract 61 61) y))
        (= ((_ extract 39 39) x) ((_ extract 60 60) y))
        (= ((_ extract 31 31) x) ((_ extract 59 59) y))
        (= ((_ extract 23 23) x) ((_ extract 58 58) y))
        (= ((_ extract 15 15) x) ((_ extract 57 57) y))
        (= ((_ extract  7  7) x) ((_ extract 56 56) y))
      )
    )
  )
)

(check-sat)
(get-model)

А теперь давайте спросим доказателя теорем Z3, является ли это теоремой:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

Результат:

sat
(model
  (define-fun mask () (_ BitVec 64)
    #x8080808080808080)
  (define-fun multiplicand () (_ BitVec 64)
    #x0002040810204081)
)

Бинго! Воспроизводит результат, указанный в оригинальном сообщении, за 0,06 секунды.

Рассматривая это в более общей перспективе, мы можем рассматривать это как пример проблемы синтеза программ первого порядка, которая является зарождающейся областью исследований, о которой было опубликовано несколько статей. Поиск "program synthesis" filetype:pdfдолжен начать вас.

Каждый 1-бит в множителе используется для копирования одного из битов в правильную позицию:

• 1уже в правильном положении, поэтому умножьте на 0x0000000000000001.
• 2необходимо сдвинуть 7-битные позиции влево, поэтому мы умножаем на 0x0000000000000080(бит 7 установлен).
• 3необходимо сдвинуть 14-битные позиции влево, поэтому мы умножаем на 0x0000000000000400(бит 14 установлен).
• и так до
• 8необходимо сместить 49-битные позиции влево, поэтому мы умножаем на 0x0002000000000000(бит 49 установлен).

Множитель является суммой множителей для отдельных битов.

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

Обратите внимание, что остальные биты в оригинальном номере должны быть 0. Это может быть достигнуто путем маскировки их операцией AND.

(Я никогда не видел это раньше. Этот трюк великолепен!)

Я немного расширю утверждение Флориса о том, что при извлечении nбитов вам нужно n-1пространство между любыми непоследовательными битами:

Моя первоначальная мысль (через минуту мы увидим, как это не совсем работает) заключалась в том, что вы могли бы добиться большего: если вы хотите извлечь nбиты, у вас iвозникнет коллизия при извлечении / сдвиге битов, если у вас есть кто-либо (не -последовательный с битом i) в i-1предыдущих n-iбитах или последующих битах.

Я приведу несколько примеров для иллюстрации:

...a..b...c...Работает (никто в 2 битах после a, бит до и немного после b, и никто не в 2 битах до c):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...a.b....c...Сбой, потому что bнаходится в 2 битах после a(и попадает в чужое место, когда мы сдвигаемся a):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...b.c...Сбой, потому что bнаходится в 2 битах предшествующих c(и выталкивается в чужое место, когда мы сдвигаемся c):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d... Работает, потому что последовательные биты сдвигаются вместе:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Но у нас есть проблема. Если бы мы использовали n-iвместо этого, у n-1нас мог бы быть следующий сценарий: что, если у нас будет столкновение вне части, о которой мы заботимся, что-то, что мы бы замаскировали в конце, но чьи биты переноса заканчивают тем, что вмешивались в важный немаскированный диапазон ? (и обратите внимание: n-1требование гарантирует, что этого не произойдет, убедившись, что i-1биты после нашего немаскированного диапазона очищены, когда мы сдвигаем iбит th)

...a...b..c...d...Потенциальный отказ от перенесенных битов, cв n-1после b, но удовлетворяет n-iкритериям:

  a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......

Так почему бы нам просто не вернуться к этому требованию " n-1бит пространства"? Потому что мы можем сделать лучше :

...a....b..c...d.. Сбойn-1 теста « биты места», но работает для нашего трюка по извлечению битов:

+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......

Я не могу придумать хороший способ охарактеризовать эти поля, которые не имеют n-1пробелов между важными битами, но все же будут работать для нашей работы. Однако, поскольку мы заранее знаем, какие биты нам интересны, мы можем проверить наш фильтр, чтобы убедиться, что мы не столкнулись с битами переноса:

Сравните (-1 AND mask) * shiftс ожидаемым результатом «все единицы» -1 << (64-n)(для 64-разрядных без знака)

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

В дополнение к и без того отличным ответам на этот очень интересный вопрос, возможно, было бы полезно знать, что этот прием побитового умножения известен в сообществе компьютерных шахмат с 2007 года, где он носит название Magic BitBoards .

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

Волшебное умножение можно использовать для сопоставления этих разбросанных Kбитов с младшими Kбитами 64-битного целого числа. Эти младшие Kбиты могут затем использоваться для индексации таблицы предварительно вычисленных битовых досок, которая представляет разрешенные квадраты, к которым может фактически перемещаться фрагмент на его исходном квадрате (заботясь о блокирующих фрагментах и ​​т. Д.)

Типичный шахматный движок, использующий этот подход, имеет 2 таблицы (одну для ладей, одну для епископов, ферзей, использующих комбинацию обоих) из 64 записей (одна для квадрата происхождения), которые содержат такие предварительно вычисленные результаты. И закрытый исходный код с самым высоким рейтингом ( Houdini ), и шахматный движок с открытым исходным кодом ( Stockfish ) в настоящее время используют этот подход для своей очень высокой производительности.

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

AFAIK, очень общий подход SAT-решателя @Syzygy, не использовался в компьютерных шахматах, и при этом нет никакой формальной теории относительно существования и уникальности таких магических констант.