Извлечение битов с одним умножением
Я видел интересную технику, использованную в ответе на другой вопрос, и хотел бы понять ее немного лучше.
Нам дано 64-разрядное целое число без знака, и нас интересуют следующие биты:
1.......2.......3.......4.......5.......6.......7.......8.......
В частности, мы хотели бы переместить их в верхние восемь позиций, вот так:
12345678........................................................
Нас не волнует значение битов, обозначенных .и они не должны быть сохранены.
Решением было замаскировать ненужные биты и умножить результат на 0x2040810204081, Это, как оказывается, делает свое дело.
Насколько общий этот метод? Можно ли использовать эту технику для извлечения любого подмножества битов? Если нет, то как выяснить, работает ли метод для определенного набора битов?
Наконец, как можно найти правильный (a?) Множитель для извлечения заданных битов?
5 ответов
Очень интересный вопрос и хитрый трюк.
Давайте рассмотрим простой пример манипулирования одним байтом. Использование 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) rule: "Это всегда будет работать, если между битами будет хотя бы (N-1) пробел; или, если известен порядок битов в конечном результате, то, если бит b заканчивается в позиции m из n, ему нужно иметь нули m-1 слева и нули нм справа ".
@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бит)
...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, не использовался в компьютерных шахматах, и при этом нет никакой формальной теории относительно существования и уникальности таких магических констант.