Bit Hacking – Manipulação de Bits

Postado em por

3

Introdução

Bit Hacking nada mais é que truques usados em programação para manipulação de bits. Esses truques são os mais diversos, como detectar se um número é potência de dois, comparar bits isolados, quantidade de bits de um inteiro, inversão de bits, etc.

Nesse post veremos maneiras fáceis e eficientes para tratar problemas recorrentes em programação apenas com a manipulação de bits. Outros exemplos serão mostrados apenas por diversão.

Definições

Os pedaços de códigos aqui apresentados estão na linguagem C e por isso usei seus operadores para operações com bits. A seguinte tabela mostra os operadores utilizados nesse post:

+----------+-------------------------+
| Símbolo  |        Definição        |
+----------+-------------------------+
|    &     |       AND binário       |
+----------+-------------------------+
|    X     |        OR binário       |
+----------+-------------------------+
|    ^     |           Xor           |
+----------+-------------------------+
|    ~     |       Not binário       |
+----------+-------------------------+
|    <<    | Deslocamento à esquerda |
+----------+-------------------------+
|    >>    |  Deslocamento à direita |
+----------+-------------------------+

Quando eu falar em bit menos significativo estarei falando do primeiro bit da direita para esquerda. Do mesmo modo, o bit mais significativo é o bit mais à esquerda do número.

Estruturação

Começarei com os exemplos mais simples e dificultarei um pouco nos últimos. Todos os exemplos desse post estão nas referências [1], [2] e [3].

Calculadora

Como estaremos usando muito a base binária, é sempre bom ter uma calculadora de conversão por perto. Veja em [5] como converter números usando programas padrões do linux. Eu, pessoalmente, uso o seguinte comando para converter para a base 2:

$ echo '98 2o p' | dc
1100011

Sendo 98 o número a ser convertido.

1) Verificar se um número é par ou ímpar

Esse truque é bastante conhecido e é provável que você já tenha o visto. É comum os programadores usarem o resto da divisão por 2 para verificar se determinado número é par ou ímpar. Se o resto for zero, então o número é par, caso contrário é ímpar.

if ( (n % 2) == 0 ) printf("Número par.\n") ;

Podemos realizar a mesma comparação sem utilizar o operador de resto da divisão. Primeiramente, um número é par se ele é divisível por dois, implicando que seu bit menos significativo é zero (multiplicar por 2 desloca o número para a esquerda zerando o bit menos significativo). Caso o bit menos significativo seja 1, necessariamente o número é ímpar.

Sabendo disso, para decidir se um número é par ou ímpar basta testar se o bit menos significativo é zero ou um. Um modo de fazer isso é usar a máscara 0x1 para retornar somente esse bit, e com isso realizar o teste logo em seguida. Assim:

  01110100 (116 em binário)
& 00000001 (1 em binário)
-----------
  00000000

O 116 é um número par e por isso o resultado do AND com 1 resultou em zero. Abaixo o mesmo teste com um número ímpar:

  01100001 (97 em binário)
& 00000001 (1 em binário)
------------
  00000001

Agora temos um modo mais eficiente para decidir se um número é par ou ímpar.

   if ( n & 1 ) printf("Número ímpar.\n") ;
   else printf("Número par.\n") ;

Veja que esse truque também funciona para números negativos representados em complemento de dois (Tente entender o motivo :D).

2) Teste do n-ésimo bit

O problema aqui é testar se determinado bit numa posição n está ativo ou não. No exemplo anterior fizemos isso, mas somente para o primeiro bit. Agora iremos expandir esse conceito para qualquer bit.

Basicamente iremos usar a máscara (1<<n) para testar se o bit na posição n está setado. Vale a pena lembrar que o primeiro bit (o bit-0) está na posição n=0. Em seguida realizamos um AND binário com essa máscara e o número, e o resultado irá nos dizer se o bit está setado ou não. É fácil perceber que se o resultado for zero, o bit não está setado, caso contrário ele está.

  01001001 (73 em binário)
& 00001000 (1<<3), para testar o bit-3
---------------
  00001000 (2^3)

Nesse exemplo testamos se o bit-3 (o quarto bit) está ativo no número 73. A máscara nesse caso é igual a (1<<3) que é o bit 1 na posição do bit-3. O resultado é diferente de zero, indicando que o bit-3 está ativado.

Esse tipo de construção é muito útil quando os bits de um número servem para indicar estados ou propriedades.

3) Ativando o n-ésimo bit

Agora suponha que queiramos setar o bit na posição n. Para isso podemos usar o método anterior com uma ligeira modificação:

x = x | (1<<n)

O que aconteceu em relação ao exemplo anterior, é que substituímos o AND lógico pelo OR.

  01001001 (73 em binário)
| 00010000 (1<<4), para ativar o bit-4
---------------
  01011001

Para entender, você deve lembrar da tabela verdade do OR. Os bits zeros da máscara não irão modificar os bits originais (zero OR x = x) e o bit-4 estará no resultado final independente do bit correspondente do número de entrada (1 OR x = 1).

4) Desativando n-ésimo bit

Para desativar um bit na posição n de um número, devemos inverter a lógica do exemplo anterior. Primeiro negamos a máscara para que o bit zero fique na posição n e em seguida, realizamos um AND com o número original:

  01001001 (73 em binário)
| 10111111 ~(1<<6), para desativar o bit-6
---------------
  00001001

Para entender, vamos recorrer a tabela verdade do AND. A máscara é composta por uns e somente um bit zero na posição n. Os uns irão conservar os bits do número original, pois (1 AND x = x), porém o bit zero irá desativar o bit correspondente independente do valor do bit original, (0 AND x = 0).

5) Inverter o n-ésimo bit

Essa situação é útil quando você quer desativar um bit ativado ou ativar um bit desativado, ou seja, inverter seu valor. Nesse caso, vamos precisar da operação XOR cuja tabela verdade você já deve conhecer (XOR em bits iguais resulta em 0 e 1 caso contrário.)

x = x ^ (1 << n)

Um exemplo seria:

  01001001 (73 em binário)
^ 00100000 (1<<5), para inverter o bit-5
---------------
  01101001

O exemplo acima trocou o valor do bit-5 do número 73 de 0 para 1 e a mágica foi feita apenas usando um XOR. Os bits zeros da máscara não alterarão os bits originais, pois 0 XOR x = x, porém quando aplicamos XOR em 1,  o valor do bit x sempre é invertido, isso é, 1 XOR x = ~x. Uma curiosidade é que em algumas ocasiões específicas, a operação XOR é usada para simular um NOT.

Agora irei mostrar uns exemplos mais complicados e tentarei explicar o máximo possível. Os exemplos serão uma mistura das referências [1], [2] e [3].

6) Swap sem variável temporária [3]

Sempre aprendemos que para trocar o valor de duas variáveis x e y, precisamos de uma variável auxiliar t:

int x = 10, y = 20 ;
int t ;
t = x ;
x = y ;
y = t ;

Porém, podemos fazer essa operação de troca usando somente operações XOR e sem usar variáveis auxiliares, assim:

int x = 10, y = 20 ;
x = x ^ y ;
y = y ^ x ;
x = x ^ y ;
/* x = 20, y = 10 */

A troca acontece devido as propriedades da operação XOR. São elas:

Comutatividade: x ^ y ^ z = x ^ z ^ y
Anulação:  x ^ x ^ y = 0 ^ y = y

Agora vamos reescrever as instruções acima substituindo os valores, vejamos:

x = x ^ y
y = y ^ x
  = y ^ (x ^ y)
  = y ^ y ^ x
  = x
x = x ^ y
  = (x ^ y') ^ y
  = (x ^ y') ^ x
  = x ^ x ^ y'
  = y'

OBS: O valor y’ representa o valor inicial da variável y.

7) Inversão dos bits de uma word

Suponha um inteiro:

118 = 01110110

O problema consiste em inverter as posições dos bits, ou seja, o bit 0 troca com o bit 7, o bit 1 troca com o bit 6, …., bit n troca com o 7-n (um efeito semelhante seria o de “$ echo 01110110 | rev”).

O resultado será:

118 = 01110110
110 = 01101110

Eu já escrevi como realizar esse tipo de operação aqui no blog, consulte a referência [4] para saber como.

8) Encontrar o valor mínimo entre dois inteiros

Dado x e y, iremos simular a função min(x,y) que retorna x se x < y ou y caso contrário.

int x = 10, y = 20;
int r ; // pega o resultado
r = y ^ ( (x ^ y) & -(x < y) ) ;

Para entender como funciona é só você lembrar das propriedades do XOR que citei acima. Vamos entender através de exemplos. Primeiro farei para x < y e depois para y <= x.

se x < y
r = y ^ ( (x ^ y) & -(x < y) )
  = y ^ ( (x ^ y) & -1 ) // -1 = 11111..11 (tudo um)
  = y ^ ( x ^ y )
  = y ^ y ^ x
  = x

se y <= x
r = y ^ ( (x ^ y) & -(x < y) )
  = y ^ ( (x ^ y) & -0 ) // -0 = 0 :)
  = y ^ 0
  = y

A mesma lógica pode ser usada para elaborar a função max(x,y). (Fica como exercício ;e)

9) Determinar se um inteiro é potência de 2

Essa dica pode ser útil em algumas situações. Antes de tudo vamos ver como se parecem as potências de dois:

2^0  = 1    = 00000001
2^1  = 2    = 00000010
2^2  = 4    = 00000100
2^3  = 8    = 00001000
2^4  = 16   = 00010000
2^5  = 32   = 00100000
...
etc

Visualmente vemos que as potências de dois contêm um único bit 1 na posição n e todos os outros bits são zeros. O bit na posição n forma a potência 2^n.

Para verificar se um número v é uma potência de dois, uma opção seria contar todos os bits 1 do inteiro, e retornar verdadeiro se essa quantidade for 1. Porém contar bits exige loops ou bit hackings mais avançados [2].

A lógica aqui é a seguinte:

f = v && !(v & (v - 1)) // f == 1 se v é potência de 2

O v-1 inverte os bits zeros de v até encontrar o primeiro bit 1 e o resultado será a negação de todos os bits antes desse bit 1, incluindo esse bit.

v   = 00010000
v-1 = 00001111

Fazendo-se, então, v&v-1 para um v potência de dois, o resultado será zero.

Para v não potência de dois, o número v tem pelo menos dois bits 1. Fazendo v-1, os bits da posição zero até o bit 1 mais à direita serão invertidos, enquanto os bits restantes não serão tocados.

v   = 01010000
v-1 = 01001111

Nesse caso, para v não potência de dois, o resultado de v&v-1 é diferente de zero.

Somente analisando o resultado de v&v-1 é necessário para validar se um número é potência de dois ou não. A parte inicial, o “v&&”, é para que se retorne falso caso v seja zero, pois esse número não é potência de dois.

Para entender melhor, vamos aos exemplos:

v = 2^4  = 00010000
v-1      = 00001111 (&)
              ^^^^^
           bits invertidos
v & v-1  = 00000000
----------------------------
v = 72   = 01001000
v-1      = 01000111 (&)
               ^^^^
            bits invertidos
v & v-1  = 01000000
           ^^^^
        não foram modificados

Referências

[1] Low Level Bit Hacks You Absolutely Must Know, by Peteris Krumins (Acessado em: Abril/2012)
http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

[2] Bit Twiddling Hacks, by Sean Eron Anderson (Acessado em: Abril/2012)
http://graphics.stanford.edu/~seander/bithacks.html

[3] A magia dos Bits by Cooler_ (Acessado em: Abril/2012)
http://coolerlab.wordpress.com/2011/11/24/a-magia-dos-bits/

[4] Inversão Dos Bits De Uma Word, by Daemonio (Acessado em: Abril/2012)
https://daemoniolabs.wordpress.com/2011/05/28/inversao-dos-bits-de-uma-word-2/

[5] Mudança de Base No Linux, by Daemonio (Acessado em: Abril/2012)
https://daemoniolabs.wordpress.com/2011/09/15/mudanca-de-base-no-linux/

3 pensamentos sobre “Bit Hacking – Manipulação de Bits”

Deixe um comentário