Invertendo um número de n bits em O (log n)

Ehud Tamir Blocked Desbloquear Seguir Seguindo 29 de dezembro de 2018

Na semana passada, enquanto escrevia meu post anterior , me deparei com um algoritmo interessante para reverter um inteiro. Por exemplo, leva 10100011 e o transforma em 11000101 . O que é legal sobre esse algoritmo é que ele faz isso nas iterações O (log n). Este é o código:

Reverte um número de n bits em O (log n). De http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

Sim. 9 linhas, incluindo chaves de assinatura e fechamento. Vamos ver como isso funciona.

A próxima parte estuda o código linha por linha. Se você está entediado com os detalhes técnicos, fique à vontade para pular para a animação no final.

Atualização: A complexidade do tempo de execução do O (log n) se aplica somente a n ? tamanho da palavra da máquina, que normalmente é de 64 bits atualmente. Obrigado a todas as pessoas que me chamaram a atenção.

A técnica: troca de blocos recursiva

O algoritmo funciona trocando recursivamente blocos adjacentes de bits, diminuindo o tamanho do bloco em cada iteração. Ele começa trocando 2 blocos de n / 2 bits, depois 4 blocos de n / 4 bits, 8 blocos de n / 8 bits e assim por diante, terminando com n blocos de 1 bit. Em cada iteração, todos os pares de blocos adjacentes são trocados em paralelo . O resultado é o número invertido. Para trocar os blocos em paralelo, o algoritmo usa operações bit-wise e máscaras de bit .

NOTA : O código original usa uma entrada de 32 bits. Usaremos inteiros de 8 bits para facilitar o entendimento.

Trocando blocos adjacentes de bits

A troca de blocos em paralelo é feita com uma máscara de bits especialmente criada.

Para um bloco de tamanho s , o bit de máscara mask é composta de blocos alternados de s zeros e s aqueles. Por exemplo, para s = 4 , mask == 00001111 . Para s = 2 , mask == 00110011 .

Esta linha usa a máscara para trocar todos os pares de blocos em paralelo :

 num = ((num >> s) e máscara) | ((num << << s) e ~ mascara); 
  • (num >> s) & mask) move os mesmo blocos s posições para a direita e limpa os blocos estranhos usando a máscara.
  • (num << s) & ~mask move os blocos ímpares s posições à esquerda e limpa os mesmo blocos usando o bit a bit NOT da máscara.
  • OU em bits é usado para adicionar esses resultados juntos no número trocado.

Incrivelmente simples, não é?

Uma flor XORed contra si mesmo. Original Por Sam Oth (Usuário: World Trekker) – Trabalho Próprio, CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=863943

Criando a máscara

Outro truque legal está em como a mask é criada. mask é composta de blocos alternados de 0s e 1s de tamanho s cada. A máscara começa como um número all-1s e atualizada na primeira linha do loop:

 while ((s >> = 1)> 0) { 
máscara ^ = (máscara << s);
...

Isso acontece logo depois que o s é dividido pela metade, então s é metade do tamanho do bloco da mask . Na primeira iteração, mask == 11111111 e s == 4 . A máscara é atualizado por XORing-se com uma outra cópia de si mesmo deixou-desviado por s lugares:

 mask = 
11111111 XOR // mask
11110000 // mask << s
= 00001111

XOR de dois bits é 1 se-e-só-se eles não são iguais uns aos outros. Em cada iteração da atualização de máscara, todos os blocos são deslocados para a esquerda pela metade do tamanho deles. Quando um bloco é XORed com a máscara anterior, metade do bloco se sobrepõe a zeros e a outra metade se sobrepõe a uns. Isso cria 2 blocos na nova máscara, cada metade do tamanho dos blocos anteriores. Aqui está uma ilustração:

 0000000011111111 // máscara original, blocos de 8 bits 
0000111111110000 // mask deslocado para a esquerda por tamanho de bloco / 2
0000111100001111 // XORed: nova máscara, blocos de 4 bits

Amarrando tudo junto

Aqui está uma breve animação que mostra o algoritmo em ação: