Inversão Dos Bits De Uma Word

Introdução

Nesse post mostrarei um método para inverter os bits de uma word. Quando falo inverter, não estou dizendo em “notear” os bits, mas sim trocá-los de posição. O bit menos significativo irá para a posição mais significativa e por aí vai.

A inspiração

Em um belo dia acesso minha máquina linux e recebo um curioso fortune[1]:

 n = ((n >>  1 ) & 0x55555555)  | ((n <<  1 )  & 0xaaaaaaaa);
 n = ((n >>  2 ) & 0x33333333)  | ((n <<  2 )  & 0xcccccccc);
 n = ((n >>  4 ) & 0x0f0f0f0f)  | ((n <<  4 )  & 0xf0f0f0f0);
 n = ((n >>  8 ) & 0x00ff00ff)  | ((n <<  8 )  & 0xff00ff00);
 n = ((n >> 16 ) & 0x0000ffff)  | ((n << 16 )  & 0xffff0000);

-- Reverse the bits in a word.

Como estava sem tempo, salvei o fortune para posterior análise. Como achei o código interessante, resolvi criar esse post.

O conceito

Como não sou um matemático e nem nada, apenas um curioso, testei o código acima com algumas entradas com a finalidade de achar um padrão. Depois de algumas tentativas descobri a lógica principal do processo.

Antes de tudo devemos consolidar o conceito por trás do fortune: os bits de n são invertidos em 5 passos. A cada passo um resultado é gerado e ele é armazenado no próprio n. No primeiro passo todos os bits vizinhos são trocados de lugar, isso é, todos os bits nas posições pares (obs: bit menos significativo ocupa a posição zero) são deslocados para posições ímpares, e os antigos bits das posições ímpares vão para posições pares. Na segunda instrução, os bits são agrupados em conjuntos, sendo cada conjunto com dois bits. O mesmo processo que ocorreu na primeira instrução vai ocorrer agora, mas ao invés de trocar a paridade das posições de bits isolados, iremos trocar a paridade dos conjuntos de dois bits. Uma visão detalhada nas outras instruções, percebemos que esse processo continua o mesmo, exceto que a quantidade de bits por conjunto aumenta. Na terceira instrução o conjunto tem 4 bits, na quarta tem 8 e na última, 16.

A sequência abaixo exemplifica todo o processo:

n = 0xBEBAC0CA (ou 10111110101110101100000011001010 em binário)

1)
10111110101110101100000011001010
01111101011101011100000011000101

Troca-se os bits em posições n com n+1 para n=0,2,4,6,8,…,30

2)
01111101011101011100000011000101 (resultado anterior)
11010111110101010011000000110101

Troca-se os bits (n, n+1) com (n+2, n+3) para n=0,4,8,12,16…,28

3)
11010111110101010011000000110101 (resultado anterior)
01111101010111010000001101010011

Troca-se os bits (n,n+1,n+2,n+3) com (n+4,n+5,n+6,n+7) para n=0,8,16,24

4)
01111101010111010000001101010011 (resultado anterior)
01011101011111010101001100000011

Troca-se os bits (n,n+1,n+2,n+3,n+4,n+5,n+6,n+7) com (n+8,n+9,n+10,n+11,n+12,n+13,n+14,n+15) para n=0,16

5)
01011101011111010101001100000011 (resultado anterior)
01010011000000110101110101111101 (resultado final)

Por fim, troca-se os 16 primeiros bits com os 16 últimos (ou seja, troca-se as metades
de lugar).

Após o passo 5 temos a word de entrada invertida. O número binário:

01010011000000110101110101111101

ou 0x53035D7D(em hexa) nada mais é que o número obtido quando se inverte os bits de 0xBEBAC0CA.

Como prova intuitiva, observe abaixo como o bit mais significativo do primeiro número é igual ao bit menos significativo do segundo (para generalizar: o n-ésimo bit mais significativo do primeiro é igual ao n-ésimo bit menos significativo do segundo):

10111110101110101100000011001010 0xBEBAC0CA
01010011000000110101110101111101 0x53035D7D

Deslocamentos, máscaras e operações de baixo nível

Todos os passos no código do fortune foram feitos por operações binárias de baixo nível. Para ser mais específico, as operações utilizadas foram deslocamento, AND e OR. Para entender o porquê delas, vamos olhar o primeiro passo. Nesse passo os bits são trocados de posição, isto é, bits em posições pares vão para posições ímpares (ex: bit-0 vai para a posição do bit-1) e vice-versa. Para fazer essa inversão, precisamos saber quais são os bits em posições pares e quais são aqueles em posições ímpares. Usando uma máscara para cada caso e utilizando a operação AND, conseguimos selecionar esses bits específicos.

Com esses bits em mãos agora só temos que trocá-los de posição. Há dois modos de fazer isso: ou aplicamos a máscara diretamente em n e deslocamos o resultado ou deslocamos n e depois aplicamos a máscara. O código do fortune deu preferência para essa segunda forma, então será ela que usarei aqui.

Sendo assim, para selecionarmos os bits em posições pares, deslocamos n uma vez para à direita de modo que o segundo bit agora seja o primeiro. Com esse deslocamento, os bits em posições pares foram parar em posições ímpares. Após o deslocamento ainda existem bits em posições ímpares ativados, então para selecionar somente os bits pares, usamos a máscara:

01010101010101010101010101010101 (ou 0x55555555)

Essa máscara seleciona os bits em posições pares, apesar dos 1’s estarem em posições ímpares. As posições pares são selecionadas por essa máscara porque anteriormente aconteceu um deslocamento para a direita.

Agora os bits em posições ímpares. Para isso temos que colocar o bit menos significativo em uma posição acima, logo isso sugere um deslocamento para a esquerda. Após o deslocamento, usamos a seguinte máscara para ativar somente os bits em posições ímpares:

10101010101010101010101010101010 (ou 0xaaaaaaaa)

Até agora temos dois resultados, pois cada máscara foi aplicada para o mesmo n. Só nos falta agora juntarmos esses resultados. Para tal tarefa basta utilizarmos a operação binária OR. Note que, ao se juntar os resultados com o OR, nenhuma operação “1 OR 1” é feita (somente “1 OR 0” ou “0 OR 1”, pois as posições que uma máscara habilita, a outra desabilita.

Bem, o que vimos até aqui foi a explicação referente a primeira instrução. Entretanto, como se pode notar, o mesmo processo ocorre na segunda instrução. Nela, o deslocamento agora é de 2, pois estamos manipulando conjuntos de 2 bits e os bits ativos das máscaras estão presentes a cada 2 posições (0,1), (3, 4), etc.

Abaixo uma tabela relacionando o número da instrução com a quantidade de bits por conjunto, por deslocamento e os valores das máscaras:

+-----+------------------+-------------+------------+--------------+
|Inst |Bits por Conjunto |Deslocamento |Mascara Par |Mascara Impar |
+-----+------------------+-------------+------------+--------------+
|  1  |        1         |      1      | 0x55555555 |  0xaaaaaaaa  |
+-----+------------------+-------------+------------+--------------+
|  2  |        2         |      2      | 0x33333333 |  0xcccccccc  |
+-----+------------------+-------------+------------+--------------+
|  3  |        4         |      4      | 0x0f0f0f0f |  0xf0f0f0f0  |
+-----+------------------+-------------+------------+--------------+
|  4  |        8         |      8      | 0x00ff00ff |  0xff00ff00  |
+-----+------------------+-------------+------------+--------------+
|  5  |        16        |     16      | 0x0000ffff |  0xffff0000  |
+-----+------------------+-------------+------------+--------------+

Só lembrando: para selecionar, por exemplo, os conjuntos em posições pares, deslocamos a quantidade de bits desses conjunto para a direita e aplicamos a primeira máscara.

Código

/* [reverse_bits.c]
 * Inverte os bits de uma word. O bit-0 se tornará
 * o bit-31 e assim por diante.
 *
 * by "fortune"
 *
 * Tue Apr 12 15:17:03 BRT 2011
 * Sat May 28 16:54:14 BRT 2011
 */

#include <stdio.h>

int main() {
    int n ;
    printf("Digite um numero: ") ;
    scanf("%d", &n) ;

    n = ((n >>  1 ) & 0x55555555) | ((n <<  1 ) & 0xaaaaaaaa);
    n = ((n >>  2 ) & 0x33333333) | ((n <<  2 ) & 0xcccccccc);
    n = ((n >>  4 ) & 0x0f0f0f0f) | ((n <<  4 ) & 0xf0f0f0f0);
    n = ((n >>  8 ) & 0x00ff00ff) | ((n <<  8 ) & 0xff00ff00);
    n = ((n >> 16 ) & 0x0000ffff) | ((n << 16 ) & 0xffff0000);

    //-- Reverse the bits in a word.

    printf("%d\n", n) ;

    return 0 ;
}

Conclusão

Esse post serviu para mostrar que as operações a nível de bits são muito poderosas e que de vez em quando, mesmo se for somente por diversão, é bom saber um pouco mais sobre elas.

Referências

[1] Fortune by wikipedia (Acessado em: Julho/2012)
http://en.wikipedia.org/wiki/Fortune_(Unix)

t+