Wyodrębnianie bitów za pomocą jednego mnożenia

Widziałem ciekawą technikę zastosowaną w odpowiedzi na inne pytanie i chciałbym ją trochę lepiej zrozumieć.

Otrzymujemy 64-bitową liczbę całkowitą bez znaku i jesteśmy zainteresowani następującymi bitami:

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

W szczególności chcielibyśmy przenieść je na najwyższe osiem pozycji, w ten sposób:

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

Nie obchodzi nas wartość bitów wskazanych przez .i nie trzeba ich zachowywać.

Rozwiązanie było maskowania niepożądanych bitów i pomnożenie wyniku przez 0x2040810204081. To, jak się okazuje, załatwia sprawę.

Jak ogólna jest ta metoda? Czy tę technikę można wykorzystać do wyodrębnienia dowolnego podzbioru bitów? Jeśli nie, w jaki sposób można ustalić, czy metoda działa dla określonego zestawu bitów?

Wreszcie, jak przejść do znalezienia (a?) Poprawnego mnożnika, aby wyodrębnić dane bity?

Bardzo interesujące pytanie i sprytna sztuczka.

Spójrzmy na prosty przykład manipulacji jednym bajtem. Używanie 8-bitowego bez znaku dla uproszczenia. Wyobraź sobie, że twój numer jest xxaxxbxxi chcesz ab000000.

Rozwiązanie składało się z dwóch kroków: trochę maskowania, a następnie pomnożenia. Maska bitowa to prosta operacja AND, która zamienia nieciekawe bity w zera. W powyższym przypadku twoja maska ​​byłaby 00100100i wynik 00a00b00.

Teraz najtrudniejsza część: przekształcenie tego w ab.......

Mnożenie to kilka operacji shift-and-add. Kluczem jest umożliwienie przelewowi „przesunięcia” bitów, których nie potrzebujemy i umieszczenia tych, które chcemy we właściwym miejscu.

Mnożenie przez 4 ( 00000100) powoduje przesunięcie wszystkiego, co pozostało o 2 i prowadzi doa00b0000 . Aby dostać się bw górę, musimy pomnożyć przez 1 (aby utrzymać a we właściwym miejscu) + 4 (aby przenieść b w górę). Suma ta wynosi 5 i w połączeniu z wcześniejszymi 4 otrzymujemy magiczną liczbę 20 lub 00010100. Oryginał był 00a00b00po zamaskowaniu; mnożenie daje:

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

Dzięki takiemu podejściu możesz objąć większą liczbę i więcej bitów.

Jedno z zadanych przez Ciebie pytań brzmiało: „czy można tego dokonać za pomocą dowolnej liczby bitów?” Myślę, że odpowiedź brzmi „nie”, chyba że zezwolisz na kilka operacji maskowania lub kilka multiplikacji. Problemem jest kwestia „kolizji” - na przykład „bezpańskie b” w powyższym problemie. Wyobraź sobie, że musimy to zrobić z taką liczbąxaxxbxxcx . Zgodnie z wcześniejszym podejściem, pomyślałbyś, że potrzebujemy {x 2, x {1 + 4 + 16}} = x 42 (oooh - odpowiedź na wszystko!). Wynik:

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

Jak widać, nadal działa, ale „tylko”. Kluczową kwestią jest tutaj to, że między „bitami” jest wystarczająco dużo miejsca, aby wszystko wycisnąć. Nie mogłem dodać czwartego bitu zaraz po c, ponieważ dostałbym przypadki, w których dostaję c + d, bity mogą przenosić ...

Więc bez formalnego dowodu odpowiedziałbym na bardziej interesujące części twojego pytania w następujący sposób: „Nie, to nie zadziała dla dowolnej liczby bitów. Aby wyodrębnić N bitów, potrzebujesz (N-1) spacji między bitami, które chcesz wyodrębnij lub wykonaj dodatkowe kroki pomnożenia maski ”.

Jedyny wyjątek, jaki mogę wymyślić w przypadku reguły „musi mieć (N-1) zera między bitami”, to: jeśli chcesz wyodrębnić dwa bity sąsiadujące ze sobą w oryginale ORAZ chcesz zachować je w w tej samej kolejności, nadal możesz to zrobić. Dla celów reguły (N-1) liczą się one jako dwa bity.

Jest jeszcze jeden wgląd - zainspirowany odpowiedzią @Ternary poniżej (zobacz mój komentarz tam). Dla każdego interesującego bitu potrzebujesz tylko tyle zer po prawej stronie, ile potrzebujesz miejsca na bity, które muszą tam przejść. Ale potrzebuje też tylu bitów po lewej, co bitów wynikowych po lewej. Więc jeśli bit b kończy się w pozycji m n, to musi mieć m-1 zera po lewej, a nm zera po prawej. Jest to ważne ulepszenie pierwotnych kryteriów, zwłaszcza gdy bity nie są w tej samej kolejności w oryginalnym numerze, co będą po ponownym uporządkowaniu. Oznacza to na przykład 16-bitowe słowo

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

Można zmienić na

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

nawet jeśli między e i b jest tylko jedna przestrzeń, dwie między d i c, trzy między pozostałymi. Co się stało z N-1? W tym przypadku a...estaje się „jednym blokiem” - są one mnożone przez 1, aby znaleźć się w odpowiednim miejscu, a więc „dostaliśmy e za darmo”. To samo dotyczy b i d (b potrzebuje trzech spacji w prawo, d potrzebuje tych samych trzech po lewej). Kiedy więc obliczamy magiczną liczbę, okazuje się, że istnieją duplikaty:

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

Oczywiście, jeśli chcesz te liczby w innej kolejności, będziesz musiał je dalej rozmieścić. Możemy przeformułować(N-1) zasadę: „Zawsze zadziała, jeśli między bitami są przynajmniej (N-1) spacje; lub, jeśli znana jest kolejność bitów w wyniku końcowym, to jeśli bit b znajdzie się w pozycji m n, musi mieć zero m-1 po lewej stronie, a nm zero po prawej stronie. ”

@Ternary zwrócił uwagę, że ta reguła nie do końca działa, ponieważ może wystąpić przeniesienie z bitów, dodając „tuż po prawej stronie obszaru docelowego” - mianowicie, gdy wszystkie szukane bity są jednymi. Kontynuując przykład podałem powyżej z pięcioma ciasno upakowanymi bitami w 16-bitowym słowie: jeśli zaczniemy

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

Dla uproszczenia wymienię pozycje bitów ABCDEFGHIJKLMNOP

Matematyka, którą zamierzaliśmy zrobić, była

ABCDEFGHIJKLMNOP

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

Do tej pory uważaliśmy, że cokolwiek poniżej abcde(pozycje ABCDE) nie będzie miało znaczenia, ale w rzeczywistości, jak wskazał @Ternary, jeśli b=1, c=1, d=1wtedy (b+c)pozycja Gspowoduje trochę przeniesienia do pozycji F, co oznacza, że (d+1)pozycja Fspowoduje przeniesienie nieco do pozycjiE - i nasze wynik jest zepsuty. Zwróć uwagę, że miejsce po prawej stronie najmniej znaczącego elementu zainteresowania (c w tym przykładzie) nie ma znaczenia, ponieważ mnożenie spowoduje wypełnienie zerami od jednego najmniej znaczącego bitu.

Musimy więc zmodyfikować naszą zasadę (m-1) / (nm). Jeśli jest więcej niż jeden bit, który ma „dokładnie (nm) nieużywane bity po prawej stronie (nie licząc ostatniego bitu we wzorze -„ c ”w powyższym przykładzie), musimy wzmocnić regułę - i musimy zrób to iteracyjnie!

Musimy spojrzeć nie tylko na liczbę bitów, które spełniają kryterium (nm), ale także na te, które są w (n-m + 1) itd. Nazwijmy ich liczbę Q0 (dokładnie n-mdo następnego bitu), Q1 ( n-m + 1), do Q (N-1) (n-1). W takim razie ryzykujemy, że nie

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

Jeśli spojrzysz na to, możesz zauważyć, że jeśli napiszesz proste wyrażenie matematyczne

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

a wynik jest taki W > 2 * N, że musisz podnieść kryterium RHS o jeden bit do (n-m+1). W tym momencie operacja jest bezpieczna, dopóki W < 4; jeśli to nie zadziała, zwiększ jeszcze jedno kryterium itp.

Myślę, że postępowanie zgodnie z powyższym da ci długą drogę do odpowiedzi ...

Rzeczywiście bardzo interesujące pytanie. Wchodzę z moimi dwoma centami, to znaczy, że jeśli potrafisz określić takie problemy w zakresie logiki pierwszego rzędu w teorii bitvectora, to dowody twierdzeń są twoim przyjacielem i mogą potencjalnie zapewnić ci bardzo szybko odpowiedzi na twoje pytania. Ponownie określmy zadany problem jako twierdzenie:

„Istnieje kilka 64-bitowych stałych„ maska ​​”i„ multiplikacja ”, tak że dla wszystkich 64-bitowych wektorów bitowych x, w wyrażeniu y = (x & mask) * multiplicand, mamy to y.63 == x.63 , y.62 == x.55, y.61 == x.47 itd. ”

Jeśli to zdanie jest w rzeczywistości twierdzeniem, to prawdą jest, że niektóre wartości stałych „mask” i „multiplicand” spełniają tę właściwość. Sformułujmy to w kategoriach czegoś, co może zrozumieć przysłowie twierdzeń, a mianowicie danych wejściowych 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)

A teraz zapytajmy przysłowie twierdzenia Z3, czy jest to twierdzenie:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

Wynik to:

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

Bingo! Odtwarza wynik podany w oryginalnym poście w 0,06 sekundy.

Patrząc na to z bardziej ogólnej perspektywy, możemy postrzegać to jako przykład problemu syntezy programu pierwszego rzędu, który jest rodzącym obszarem badań, na temat którego opublikowano niewiele artykułów. Poszukiwanie "program synthesis" filetype:pdfpowinno zacząć.

Każdy 1-bit w multiplikatorze służy do skopiowania jednego z bitów do jego właściwej pozycji:

• 1jest już w prawidłowej pozycji, więc pomnóż przez 0x0000000000000001.
• 2 należy przesunąć o 7 bitów w lewo, więc mnożymy przez 0x0000000000000080 (bit 7 jest ustawiony).
• 3należy przesunąć o 14 bitów w lewo, więc mnożymy przez 0x0000000000000400(bit 14 jest ustawiony).
• i tak dalej
• 8należy przesunąć o 49 bitów w lewo, więc mnożymy przez 0x0002000000000000(bit 49 jest ustawiony).

Mnożnik jest sumą mnożników dla poszczególnych bitów.

Działa to tylko dlatego, że bity, które mają być zebrane, nie są zbyt blisko siebie, tak że zwielokrotnienie bitów, które nie pasują do siebie w naszym schemacie, albo wykracza poza 64-bitowy, albo w dolnej części, na której nie ma znaczenia.

Zauważ, że pozostałe bity w pierwotnym numerze muszą być 0. Można to osiągnąć poprzez maskowanie ich operacją AND.

(Nigdy wcześniej tego nie widziałem. Ta sztuczka jest świetna!)

Rozbuduję trochę twierdzenie Florisa, że ​​podczas wydobywania nbitów potrzebujeszn-1 odstępu między dowolnymi nieciągłymi bitami:

Moją początkową myślą (za chwilę zobaczymy, jak to nie do końca działa) było to, że możesz zrobić lepiej: jeśli chcesz wyodrębnić nbity, będziesz mieć kolizję podczas wydobywania / przesuwania bitu, ijeśli masz kogoś (nie -konsekwentne z bitem i) w i-1bitach poprzedzających lub n-ibitach późniejszych.

Podam kilka przykładów ilustrujących:

...a..b...c... Działa (nikt w 2 bitach później a , trochę wcześniej i trochę później bi nikt nie jest w 2 bitach później c):

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

...a.b....c... Nie działa, ponieważ b działa, znajduje się w 2 bitach później a(i zostaje wciągnięty w miejsce kogoś innego, gdy się zmieniamy a):

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

...a...b.c... Nie działa, ponieważ b działa, znajduje się w 2 bitach poprzedzających c(i zostaje zepchnięty w miejsce kogoś innego podczas zmiany c):

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

...a...bc...d... Działa, ponieważ kolejne bity przesuwają się razem:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Ale mamy problem. Jeśli użyjemy n-izamiastn-1 , moglibyśmy mieć następujący scenariusz: co gdybyśmy mieli kolizję poza częścią, na której nam zależy, coś, co chcielibyśmy ukryć na końcu, ale którego bity przenoszące ostatecznie zakłócają ważny, nie maskowany zakres ? (i uwaga: n-1wymaganie upewnia się, że tak się nie stanie, upewniając się, że i-1bity po naszym nie zamaskowanym zakresie są czyste, gdy zmieniamyi th th)

...a...b..c...d...Potencjalna awaria bitów przenoszących cwystępujen-1 później b, ale spełnia n-ikryteria:

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

Dlaczego więc nie wrócimy do tego ”n-1 wymogu kawałków przestrzeni”? Ponieważ możemy zrobić lepiej :

...a....b..c...d.. Nie powiedzie się „n-1 test bitów przestrzeni”, ale działa na naszą sztuczkę wyodrębniania bitów:

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

Nie mogę znaleźć dobrego sposobu na scharakteryzowanie tych pól, które tego nie robią ma n-1miejsca między ważnymi bitami, ale nadal działałyby dla naszej operacji. Ponieważ jednak wiemy z góry które bity jesteśmy zainteresowani, możemy sprawdzić nasz filtr, aby upewnić się, że nie występują kolizje bitów przenoszących:

Porównaj (-1 AND mask) * shiftz oczekiwanym wynikiem wszystkich,-1 << (64-n) (dla wersji 64-bitowej bez znaku)

Przesunięcie / pomnożenie magii w celu wyodrębnienia naszych bitów działa tylko wtedy, gdy oba są równe.

Oprócz doskonałych odpowiedzi na to bardzo interesujące pytanie, warto wiedzieć, że ta sztuczka polegająca na multiplikacji bitowej jest znana w społeczności szachów komputerowych od 2007 roku, pod nazwą Magic BitBoards .

Wiele komputerowych silników szachowych używa kilku 64-bitowych liczb całkowitych (zwanych bitboardami) do reprezentowania różnych zestawów sztuk (1 bit na zajmowany kwadrat). Załóżmy, że przesuwany element (wieża, biskup, królowa) na pewnym polu początkowym może przejść do co najwyżej Kkwadratów, jeśli nie było żadnych blokujących elementów. Używanie Kbitów -i tych rozproszonych bitów z bitboardem zajmowanych kwadratów daje określone K-bitowe słowo osadzone w 64-bitowej liczbie całkowitej.

Magicznego mnożenia można użyć do odwzorowania tych rozproszonych Kbitów na niższe Kbity 64-bitowej liczby całkowitej. Te niższe Kbity można następnie wykorzystać do indeksowania tabeli wstępnie obliczonych bitboardów, które reprezentują dozwolone kwadraty, do których może faktycznie przenieść się kawałek na jego pierwotnym kwadracie (dbając o blokowanie elementów itp.)

Typowy silnik szachowy wykorzystujący to podejście ma 2 tabele (jeden dla wież, jeden dla biskupów, królowe używające kombinacji obu) z 64 wpisami (jeden dla kwadratu początkowego), które zawierają takie wstępnie obliczone wyniki. Zarówno najwyżej oceniane zamknięte źródło ( Houdini ), jak i silnik szachowy typu open source ( Sztokfisz ) obecnie stosują to podejście ze względu na bardzo wysoką wydajność.

Znalezienie tych magicznych mnożników odbywa się albo za pomocą wyczerpującego wyszukiwania (zoptymalizowanego z wczesnymi odcięciami), albo za pomocą prób i błędów (np. wielu losowych 64-bitowych liczb całkowitych). Podczas generowania ruchów nie użyto żadnych wzorów bitów, dla których nie można było znaleźć stałej magicznej. Jednak bitowe efekty przenoszenia są zwykle konieczne, gdy bity do mapowania mają (prawie) sąsiednie indeksy.

AFAIK, bardzo ogólne podejście do SAT-Solvera autorstwa @Syzygy, nie było używane w szachach komputerowych i nie wydaje się też, aby istniała formalna teoria dotycząca istnienia i wyjątkowości takich magicznych stałych.