Extraindo bits com uma única multiplicação

Vi uma técnica interessante usada em resposta a outra pergunta e gostaria de entender um pouco melhor.

Recebemos um número inteiro de 64 bits não assinado e estamos interessados ​​nos seguintes bits:

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

Especificamente, gostaríamos de movê-los para as oito primeiras posições, assim:

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

Não nos importamos com o valor dos bits indicados por .e eles não precisam ser preservados.

A solução foi mascarar os bits indesejados e multiplicar o resultado por 0x2040810204081. Acontece que isso funciona.

Quão geral é esse método? Essa técnica pode ser usada para extrair qualquer subconjunto de bits? Caso contrário, como descobrir se o método funciona ou não para um conjunto específico de bits?

Por fim, como encontrar o multiplicador (a?) Correto para extrair os bits fornecidos?

Pergunta muito interessante e truque inteligente.

Vejamos um exemplo simples de como manipular um único byte. Usando 8 bits não assinados para simplificar. Imagine seu número xxaxxbxxe você deseja ab000000.

A solução consistiu em duas etapas: um pouco de máscara, seguida de multiplicação. A máscara de bits é uma operação AND simples que transforma bits desinteressantes em zeros. No caso acima, sua máscara seria 00100100e o resultado 00a00b00.

Agora a parte mais difícil: transformar isso em ab.......

Uma multiplicação é um monte de operações de troca e adição. A chave é permitir que o excesso "desvie" os bits de que não precisamos e coloque os que queremos no lugar certo.

A multiplicação por 4 ( 00000100) mudaria tudo o que restava por 2 e o levaria a00b0000. Para bsubir, precisamos multiplicar por 1 (para manter a no lugar certo) + 4 (para subir b). Essa soma é 5 e, combinada com as 4 anteriores, obtemos um número mágico de 20 ou 00010100. O original foi 00a00b00depois de mascarar; a multiplicação dá:

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

A partir dessa abordagem, você pode estender para números maiores e mais bits.

Uma das perguntas que você fez foi "isso pode ser feito com qualquer número de bits?" Eu acho que a resposta é "não", a menos que você permita várias operações de mascaramento ou várias multiplicações. O problema é a questão das "colisões" - por exemplo, o "b perdido" no problema acima. Imagine que precisamos fazer isso com um número parecido xaxxbxxcx. Seguindo a abordagem anterior, você pensaria que precisamos de {x 2, x {1 + 4 + 16}} = x 42 (oooh - a resposta para tudo!). Resultado:

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

Como você pode ver, ainda funciona, mas "apenas". A chave aqui é que existe "espaço suficiente" entre os bits que queremos que possamos espremer tudo. Eu não poderia adicionar um quarto bit d logo após c, porque eu receberia instâncias em que eu recebia c + d, os bits poderiam carregar, ...

Portanto, sem prova formal, eu responderia as partes mais interessantes da sua pergunta da seguinte maneira: "Não, isso não funcionará para nenhum número de bits. Para extrair N bits, você precisa de espaços (N-1) entre os bits que deseja extrair ou ter etapas adicionais de multiplicação de máscara ".

A única exceção que posso pensar para a regra "deve ter (N-1) zeros entre bits" é a seguinte: se você deseja extrair dois bits adjacentes um ao outro no original, E você deseja mantê-los no diretório mesma ordem, você ainda pode fazê-lo. E para os fins da regra (N-1), eles contam como dois bits.

Há outro insight - inspirado na resposta do @Ternary abaixo (veja meu comentário lá). Para cada bit interessante, você precisa apenas de zeros à direita e de espaço para os bits que precisam ir para lá. Mas também precisa de tantos bits para a esquerda quanto de bits para a esquerda. Portanto, se um bit b termina na posição m de n, ele precisa ter m-1 zeros à esquerda e nm zeros à direita. Especialmente quando os bits não estão na mesma ordem no número original, como estarão após o novo pedido, isso é uma melhoria importante nos critérios originais. Isso significa, por exemplo, que uma palavra de 16 bits

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

Pode ser deslocado para

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

mesmo que exista apenas um espaço entre e e b, dois entre d e c, três entre os outros. O que aconteceu com o N-1 ?? Nesse caso, a...etorna-se "um bloco" - eles são multiplicados por 1 para terminar no lugar certo e, portanto, "recebemos e de graça". O mesmo vale para b e d (b precisa de três espaços à direita, d precisa dos mesmos três à sua esquerda). Então, quando calculamos o número mágico, descobrimos que existem duplicatas:

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

Claramente, se você quisesse esses números em uma ordem diferente, teria que espaçá-los ainda mais. Podemos reformular a (N-1)regra: "Sempre funcionará se houver pelo menos (N-1) espaços entre os bits; ou, se a ordem dos bits no resultado final for conhecida, se um bit b terminar na posição m de n, ele precisa ter m-1 zeros à esquerda e nm zeros à direita. "

O @Ternary apontou que essa regra não funciona muito bem, pois pode haver uma carga de bits adicionando "exatamente à direita da área de destino" - ou seja, quando os bits que estamos procurando são todos iguais. Continuando o exemplo que dei acima com os cinco bits compactados em uma palavra de 16 bits: se começarmos com

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

Para simplificar, vou nomear as posições dos bits ABCDEFGHIJKLMNOP

A matemática que íamos fazer era

ABCDEFGHIJKLMNOP

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

Até agora, pensávamos que qualquer coisa abaixo abcde(posições ABCDE) não importaria, mas, na verdade, como @Ternary apontou, se b=1, c=1, d=1então a (b+c)posição Gfará com que um pouco carregue para a posição F, o que significa que (d+1)na posição Flevará um pouco para dentro E- e nossa resultado é estragado. Observe que o espaço à direita do bit de interesse menos significativo ( cneste exemplo) não importa, pois a multiplicação causará preenchimento com zeros de além do bit menos significativo.

Portanto, precisamos modificar nossa regra (m-1) / (nm). Se houver mais de um bit com "exatamente (nm) bits não utilizados à direita (sem contar o último bit no padrão -" c "no exemplo acima), precisamos fortalecer a regra - e precisamos faça-o iterativamente!

Temos que observar não apenas o número de bits que atendem ao critério (nm), mas também os que estão em (n-m + 1), etc. Vamos chamar o número Q0 (exatamente n-mpara o próximo bit), Q1 ( n-m + 1), até Q (N-1) (n-1). Então corremos o risco de carregar se

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

Se você olhar para isso, poderá ver que, se escrever uma expressão matemática simples

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

e o resultado é W > 2 * N, então você precisa aumentar o critério RHS em um bit para (n-m+1). Neste ponto, a operação é segura enquanto W < 4; se isso não funcionar, aumente mais o critério, etc.

Penso que, seguindo o exposto acima, você obterá um longo caminho para sua resposta ...

Pergunta muito interessante mesmo. Estou concordando com meus dois centavos, ou seja, se você conseguir declarar problemas como esse em termos de lógica de primeira ordem sobre a teoria do vetor de bits, os provadores de teoremas são seus amigos e podem potencialmente fornecer-lhe muito rapidamente Respostas às suas perguntas. Vamos reiterar o problema que está sendo solicitado como um teorema:

"Existem algumas constantes de 64 bits 'mask' e 'multiplicand', tais que, para todos os vetores de 64 bits x, na expressão y = (x & mask) * multiplicando, temos esse y.63 == x.63 , y.62 == x.55, y.61 == x.47 etc. "

Se essa sentença é de fato um teorema, é verdade que alguns valores das constantes 'mascaram' e 'multiplicando' satisfazem essa propriedade. Então, vamos colocar isso em termos de algo que um provador de teoremas possa entender, a saber, a entrada 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)

E agora vamos perguntar ao provador de teoremas Z3 se este é um teorema:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

O resultado é:

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

Bingo! Ele reproduz o resultado fornecido no post original em 0,06 segundos.

Observando isso de uma perspectiva mais geral, podemos ver isso como um exemplo de um problema de síntese de programa de primeira ordem, que é uma área de pesquisa nascente sobre a qual poucos artigos foram publicados. Uma pesquisa para "program synthesis" filetype:pdfvocê deve começar.

Cada bit 1 no multiplicador é usado para copiar um dos bits na posição correta:

• 1já está na posição correta, então multiplique por 0x0000000000000001.
• 2deve ser deslocado as posições de 7 bits para a esquerda, então multiplicamos por 0x0000000000000080(o bit 7 está definido).
• 3deve ser deslocado as posições de 14 bits para a esquerda, então multiplicamos por 0x0000000000000400(o bit 14 está definido).
• e assim por diante até
• 8deve ser deslocado 49 posições de bit para a esquerda, para multiplicarmos 0x0002000000000000(bit 49 está definido).

O multiplicador é a soma dos multiplicadores para os bits individuais.

Isso funciona apenas porque os bits a serem coletados não estão muito próximos, de modo que a multiplicação de bits que não pertencem um ao outro em nosso esquema cai além dos 64 bits ou na parte inferior não importa.

Observe que os outros bits no número original devem ser 0. Isso pode ser alcançado mascarando-os com uma operação AND.

(Eu nunca tinha visto isso antes. Esse truque é ótimo!)

Vou expandir um pouco a afirmação de Floris de que, ao extrair nbits, você precisa de n-1espaço entre os bits não consecutivos:

Meu pensamento inicial (veremos em um minuto como isso não funciona) foi que você poderia fazer melhor: se você deseja extrair nbits, terá uma colisão ao extrair / mudar bits ise tiver alguém (não consecutivo com bit i) nos i-1bits anteriores ou n-isubsequentes.

Vou dar alguns exemplos para ilustrar:

...a..b...c...Funciona (ninguém nos 2 bits depois a, o antes e o depois be ninguém está nos 2 bits anteriores c):

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

...a.b....c...Falha porque bestá nos 2 bits seguintes a(e é puxado para o lugar de outra pessoa quando mudamos a):

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

...a...b.c...Falha porque bestá nos 2 bits anteriores c(e é empurrado para o lugar de outra pessoa quando mudamos c):

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

...a...bc...d... Funciona porque bits consecutivos se alternam:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Mas nós temos um problema. Se usarmos, em n-ivez de n-1, poderíamos ter o seguinte cenário: e se tivermos uma colisão fora da parte com a qual nos preocupamos, algo que esconderíamos no final, mas cujos bits de transporte acabam interferindo no importante intervalo sem máscara ? (e observe: o n-1requisito garante que isso não aconteça, certificando-se de que os i-1bits após o intervalo não mascarado sejam claros quando alteramos o ith th)

...a...b..c...d...Falha em potencial em carry-bits, cé n-1após b, mas atende aos n-icritérios:

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

Então, por que não voltamos a esse n-1requisito de " bits de espaço"? Porque podemos fazer melhor :

...a....b..c...d.. Falha no teste " n-1bits de espaço", mas funciona para o nosso truque de extração de bits:

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

Não consigo encontrar uma boa maneira de caracterizar esses campos que não têm n-1espaço entre bits importantes, mas ainda funcionariam para nossa operação. No entanto, como sabemos antecipadamente em quais bits estamos interessados, podemos verificar nosso filtro para garantir que não ocorram colisões de carry-bit:

Compare (-1 AND mask) * shiftcom o resultado esperado esperado -1 << (64-n)(para não assinado de 64 bits)

A mudança / multiplicação mágica para extrair nossos bits funciona se e somente se os dois forem iguais.

Além das respostas já excelentes para essa pergunta muito interessante, pode ser útil saber que esse truque de multiplicação bit a bit é conhecido na comunidade de xadrez para computadores desde 2007, onde é chamado Magic BitBoards .

Muitos mecanismos de xadrez de computador usam vários números inteiros de 64 bits (chamados de painéis de bit) para representar os vários conjuntos de peças (1 bit por quadrado ocupado). Suponha que uma peça deslizante (torre, bispo, rainha) em um determinado quadrado de origem possa mover-se para no máximo Kquadrados se nenhuma peça de bloqueio estiver presente. O uso bit a bit - e daqueles Kbits dispersos com o bitboard de quadrados ocupados fornece uma Kpalavra de bit específica incorporada em um número inteiro de 64 bits.

A multiplicação mágica pode ser usada para mapear esses Kbits dispersos para os Kbits inferiores de um número inteiro de 64 bits. Esses Kbits inferiores podem então ser usados ​​para indexar uma tabela de placas de bits pré-computadas que representam os quadrados permitidos para os quais a peça em seu quadrado de origem pode realmente se mover (cuidando das peças de bloqueio etc.)

Um mecanismo de xadrez típico usando essa abordagem possui 2 tabelas (uma para torres, uma para bispos e rainhas usando a combinação de ambas) de 64 entradas (uma por quadrado de origem) que contêm esses resultados pré-calculados. Atualmente, tanto a fonte fechada com classificação mais alta ( Houdini ) quanto o mecanismo de xadrez de fonte aberta ( Stockfish ) usam essa abordagem por seu desempenho muito alto.

A localização desses multiplicadores mágicos é feita usando uma pesquisa exaustiva (otimizada com cortes iniciais) ou com tentativa e erro (por exemplo, tentando muitos números aleatórios de 64 bits). Não houve padrões de bits usados ​​durante a geração de movimentos para os quais nenhuma constante mágica foi encontrada. No entanto, os efeitos de transporte bit a bit são normalmente necessários quando os bits a serem mapeados possuem (quase) índices adjacentes.

AFAIK, a abordagem muito geral do @Syzygy para resolver problemas com SAT, não foi usada no xadrez do computador e também não parece haver nenhuma teoria formal sobre a existência e a exclusividade de tais constantes mágicas.