bitwise - Extracción de bits con una sola multiplicación.

bitwise operator c++

Question

Vi una técnica interesante utilizada en una answer a otra pregunta , y me gustaría entenderla un poco mejor.

Se nos da un entero de 64 bits sin firmar, y estamos interesados ​​en los siguientes bits:

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

Específicamente, nos gustaría moverlos a las ocho mejores posiciones, así:

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

No nos importa el valor de los bits indicados por . , y no tienen que ser preservados.

La answer fue enmascarar los bits no deseados y multiplicar el resultado por 0x2040810204081 . Esto, como resulta, hace el truco.

¿Qué tan general es este método? ¿Se puede usar esta técnica para extraer cualquier subconjunto de bits? Si no es así, ¿cómo se puede determinar si el método funciona o no para un conjunto particular de bits?

Finalmente, ¿cómo se podría hacer para encontrar el multiplicador correcto (a?) Para extraer los bits dados?

Answer 1

Además de las ya excelentes respuestas a esta interesante pregunta, puede ser útil saber que este truco de multiplicación de bits se conoce en la comunidad de ajedrez por computadora desde 2007, donde se denomina Magic BitBoards .

Muchos motores de ajedrez de computadora usan varios enteros de 64 bits (llamados tableros de bits) para representar los distintos conjuntos de piezas (1 bit por cuadrado ocupado). Supongamos que una pieza deslizante (torre, alfil, reina) en un cuadrado de origen determinado puede moverse a la mayoría de los cuadrados K si no hubiera piezas de bloqueo presentes. El uso de bit a bit y de esos K bits dispersos con el tablero de bits de cuadrados ocupados da una palabra específica de K -bits incrustada dentro de un entero de 64 bits.

La multiplicación mágica se puede usar para asignar estos K bits dispersos a los K bits más bajos de un entero de 64 bits. Estos K bits inferiores se pueden usar para indexar una tabla de bitboards precalculados que representan los cuadrados permitidos a los que se puede mover la pieza en su cuadrado de origen (cuidando las piezas de bloqueo, etc.)

Un motor de ajedrez típico que utiliza este enfoque tiene 2 tablas (una para torres, una para obispos, reinas que usan la combinación de ambas) de 64 entradas (una por casilla de origen) que contienen dichos resultados precalculados. Tanto el motor de código abierto de código cerrado ( Houdini ) como el motor de ajedrez de código abierto ( Stockfish ) utilizan actualmente este enfoque por su alto rendimiento.

Encontrar estos multiplicadores mágicos se realiza mediante una búsqueda exhaustiva (optimizada con cortes tempranos) o con trial y erorr (por ejemplo, intentando muchos enteros aleatorios de 64 bits). No se han utilizado patrones de bits durante la generación de movimientos para los que no se pudo encontrar una constante mágica. Sin embargo, los efectos de transmisión a nivel de bits son típicamente necesarios cuando los bits a ser mapeados tienen índices (casi) adyacentes.

AFAIK, el enfoque muy general de la resolución SAT de @Syzygy no se ha utilizado en el ajedrez por computadora, y tampoco parece haber ninguna teoría formal con respecto a la existencia y singularidad de tales constantes mágicas.

Answer 2

Cada 1 bit en el multiplicador se usa para copiar uno de los bits en su posición correcta:

• 1 ya está en la posición correcta, por lo tanto, multiplique por 0x0000000000000001 .
• 2 deben desplazarse 7 posiciones de bit hacia la izquierda, por lo que multiplicamos por 0x0000000000000080 (el bit 7 está configurado).
• 3 deben desplazarse 14 posiciones de bit hacia la izquierda, por lo que multiplicamos por 0x0000000000000400 (el bit 14 está configurado).
• y así sucesivamente hasta
• 8 deben desplazarse 49 posiciones de bit hacia la izquierda, por lo que multiplicamos por 0x0002000000000000 (el bit 49 está configurado).

El multiplicador es la suma de los multiplicadores para los bits individuales.

Esto solo funciona porque los bits que se recolectan no están demasiado juntos, por lo que la multiplicación de los bits que no pertenecen a nuestro esquema cae más allá del 64 bit o en la parte inferior no importa.

Tenga en cuenta que los otros bits en el número original deben ser 0 . Esto se puede lograr enmascarándolos con una operación AND.

Answer 3

Pregunta muy interesante por cierto. Estoy contribuyendo con mis dos centavos, que es que, si puede resolver problemas como este en términos de lógica de primer orden sobre la teoría del vector de bits, entonces los probadores de teoremas son sus amigos y potencialmente pueden proporcionarle muy rápido. Respuestas a tus preguntas. Repetamos el problema que se plantea como un teorema:

"Existen algunas constantes de 64 bits ''máscara'' y ''multiplicando'', de modo que, para todos los vectores de bits de 64 bits x, en la expresión y = (x & máscara) * multiplicando, tenemos que y.63 == x.63 , y.62 == x.55, y.61 == x.47, etc. "

Si esta oración es de hecho un teorema, entonces es cierto que algunos valores de las constantes ''máscara'' y ''multiplicando'' satisfacen esta propiedad. Entonces expresemos esto en términos de algo que pueda entender un proverbio de teoremas, a saber, la entrada de 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)

Y ahora preguntemos al proverbio Z3 si este es un teorema:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

El resultado es:

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

¡Bingo! Reproduce el resultado dado en la publicación original en 0.06 segundos.

Si observamos esto desde una perspectiva más general, podemos ver esto como un ejemplo de un problema de síntesis de programas de primer orden, que es un área naciente de investigación sobre la cual se han publicado pocos artículos. Una búsqueda del tipo de "program synthesis" filetype:pdf debería ayudarlo a comenzar.

Answer 4

Pregunta muy interesante, y truco inteligente.

Veamos un ejemplo simple de obtener un solo byte manipulado. Usando 8 bits sin firmar para simplificar. Imagina que tu número es xxaxxbxx y quieres ab000000 .

La solución consistió en dos pasos: un poco de enmascaramiento, seguido de una multiplicación. La máscara de bits es una operación AND simple que convierte los bits no interesantes en ceros. En el caso anterior, su máscara sería 00100100 y el resultado 00a00b00 .

Ahora la parte difícil: convertir eso en ab......

Una multiplicación es un grupo de operaciones de cambio y adición. La clave es permitir que el desbordamiento "desplace" los bits que no necesitamos y coloque los que queremos en el lugar correcto.

La multiplicación por 4 ( 00000100 ) desplazaría todo lo que quedara por 2 y lo a00b0000 a a00b0000 . Para hacer que la b suba, necesitamos multiplicar por 1 (para mantener la a en el lugar correcto) + 4 (para mover la b hacia arriba). Esta suma es 5, y combinada con las 4 anteriores obtenemos un número mágico de 20, o 00010100 . El original era 00a00b00 después de enmascarar; la multiplicación da:

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

Desde este enfoque puede ampliarse a números más grandes y más bits.

Una de las preguntas que hizo fue "¿Se puede hacer esto con cualquier número de bits?" Creo que la respuesta es "no", a menos que permita varias operaciones de enmascaramiento o varias multiplicaciones. El problema es el problema de las "colisiones", por ejemplo, la "desviación b" en el problema anterior. Imagina que necesitamos hacer esto con un número como xaxxbxxcx . Siguiendo el enfoque anterior, pensarías que necesitamos {x 2, x {1 + 4 + 16}} = x 42 (oooh - ¡la respuesta a todo!). Resultado:

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

Como puede ver, todavía funciona, pero "solo justo". La clave aquí es que hay "suficiente espacio" entre los bits que queremos que podamos exprimir todo. No pude agregar un cuarto bit d justo después de c, porque obtendría instancias donde obtengo c + d, los bits podrían cargar,

Entonces, sin una prueba formal, respondería a las partes más interesantes de su pregunta de la siguiente manera: "No, esto no funcionará para cualquier número de bits. Para extraer N bits, necesita (N-1) espacios entre los bits que desea extraer, o tener más pasos multiplicar máscara ".

La única excepción que se me ocurre para la regla de "debe tener (N-1) ceros entre bits" es la siguiente: si desea extraer dos bits adyacentes entre sí en el original, Y desea mantenerlos en el mismo orden, entonces todavía puedes hacerlo. Y para los fines de la regla (N-1), cuentan como dos bits.

Hay otra idea, inspirada en la respuesta de @Ternary a continuación (vea mi comentario allí). Para cada bit interesante, solo necesita tantos ceros a la derecha como espacio necesario para los bits que deben ir allí. Pero también necesita tantos bits a la izquierda como resultados a la izquierda. Entonces, si un bit b termina en la posición m de n, entonces necesita tener ceros m-1 a su izquierda y ceros nm a su derecha. Especialmente cuando los bits no están en el mismo orden en el número original ya que estarán después de la reordenación, esta es una mejora importante con respecto al criterio original. Esto significa, por ejemplo, que una palabra de 16 bits.

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

Puede ser cambiado en

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

aunque solo hay un espacio entre e y b, dos entre d y c, tres entre los otros. ¿Qué pasó con N-1? En este caso, a...e convierte en "un bloque", se multiplican por 1 para terminar en el lugar correcto, y por lo tanto "obtenemos e de forma gratuita". Lo mismo es cierto para b y d (b necesita tres espacios a la derecha, d necesita los mismos tres a su izquierda). Entonces, cuando calculamos el número mágico, encontramos que hay duplicados:

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

Claramente, si quisieras estos números en un orden diferente, tendrías que espaciarlos más. Podemos reformular la regla (N-1) : "Siempre funcionará si hay al menos (N-1) espacios entre los bits; o, si se conoce el orden de los bits en el resultado final, entonces si un bit b finaliza arriba en la posición m de n, necesita tener ceros m-1 a su izquierda y nm ceros a su derecha ".

@Ternary señaló que esta regla no funciona del todo, ya que puede haber un acarreo desde los bits que agregan "justo a la derecha del área objetivo", es decir, cuando los bits que buscamos son todos. Continuando con el ejemplo que di anteriormente, con los cinco bits bien empaquetados en una palabra de 16 bits: si empezamos con

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

Para simplificar, ABCDEFGHIJKLMNOP posiciones de bit ABCDEFGHIJKLMNOP

La matemática que íbamos a hacer era

ABCDEFGHIJKLMNOP

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

Hasta ahora, pensamos que cualquier cosa debajo de abcde (posiciones ABCDE ) no importaría, pero de hecho, como señaló @Ternary, si b=1, c=1, d=1 entonces (b+c) en la posición G causará una bit para llevar a la posición F , lo que significa que (d+1) en la posición F llevará un bit a E , y nuestro resultado se echa a perder. Tenga en cuenta que el espacio a la derecha del bit de interés menos significativo ( c en este ejemplo) no importa, ya que la multiplicación causará el relleno con ceros desde el bit menos significativo.

Entonces necesitamos modificar nuestra regla (m-1) / (nm). Si hay más de un bit que tiene "exactamente (nm) bits no utilizados a la derecha (sin contar el último bit en el patrón -" c "en el ejemplo anterior), entonces necesitamos fortalecer la regla - y tenemos que hacerlo iterativamente!

Tenemos que observar no solo el número de bits que cumplen el criterio (nm), sino también los que están en (n-m + 1), etc. Llamemos a su número Q0 (exactamente nm al siguiente bit), Q1 (n-m + 1), hasta Q (N-1) (n-1). Entonces nos arriesgamos a llevar si

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

Si observa esto, puede ver que si escribe una expresión matemática simple

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

y el resultado es W > 2 * N , entonces necesita aumentar el criterio RHS en un bit a (n-m+1) . En este punto, la operación es segura siempre que W < 4 ; Si eso no funciona, aumenta el criterio uno más, etc.

Creo que seguir lo anterior te llevará a un largo camino para tu respuesta ...

Answer 5

(Nunca lo había visto antes. ¡Este truco es genial!)

Ampliaré un poco la afirmación de Floris de que cuando extraiga n bits, necesitará n-1 espacio n-1 entre los bits no consecutivos:

Mi idea inicial (en un minuto veremos cómo esto no funciona) fue que podrías hacerlo mejor: si quieres extraer n bits, tendrás una colisión al extraer / cambiar bit i si tienes a alguien (no consecutivo con el bit i ) en los bits i-1 anteriores o ni bits posteriores.

Daré algunos ejemplos para ilustrar:

...a..b...c... Funciona (nadie en los 2 bits después de a , el bit anterior y el bit después de b , y nadie está en los 2 bits antes de c ):

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

...ab...c... Falla porque b está en los 2 bits después de a (y es arrastrado al lugar de otra persona cuando cambiamos a ):

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

...a...bc.. Falla porque b está en los 2 bits que preceden a c (y se empuja al lugar de otra persona cuando cambiamos c ):

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

...a...bc...d... Funciona porque los bits consecutivos cambian juntos:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Pero tenemos un problema. Si utilizamos ni lugar de n-1 , podríamos tener el siguiente escenario: ¿qué pasaría si tuviéramos una colisión fuera de la parte que nos importa, algo que ocultamos al final, pero cuyos bits de acarreo terminan interfiriendo en el importante rango sin enmascarar? (y nota: el requisito n-1 asegura que esto no suceda al asegurarnos de que los bits i-1 después de nuestro rango sin máscara estén claros cuando cambiemos el bit i )

...a...b..c...d... Falla potencial en los bits de acarreo, c está en n-1 después de b , pero cumple con los criterios:

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

Entonces, ¿por qué no volvemos al requisito de " n-1 bits de espacio"? Porque podemos hacerlo mejor :

...a....b..c...d.. Falla la prueba de " n-1 bits de espacio", pero funciona para nuestro truco de extracción de bits:

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

No puedo encontrar una buena manera de caracterizar estos campos que no tengan n-1 espacio n-1 entre los bits importantes, pero que aún funcione para nuestra operación. Sin embargo, ya que sabemos de antemano en qué bits nos interesamos, podemos comprobar nuestro filtro para asegurarnos de que no experimentamos colisiones de bit de acarreo:

Comparar (-1 AND mask) * shift contra el resultado esperado de todos unos, -1 << (64-n) (para 64 bits sin firmar)

El cambio mágico / multiplicación para extraer nuestros bits funciona solo si los dos son iguales.