Paralelismo de bits

O vetor de bits (ou array de bits, bitboard, bitmap) é uma maneira de armazenar e endereçar bits diretamente. Usando essa estrutura, podemos explorar o paralelismo de bits para executar tarefas mais rapidamente e ainda reduzir os requisitos de memória.

Essa técnica está sendo aplicada com sucesso para efetuar operações sobre a matriz de adjacência de um grafo, efetuar operações sobre emparelhamentos de cadeias de caracteres e efetuar operações em jogos de tabuleiro como o xadrez.

As tarefas podem ser executadas mais rapidamente por causa da correspondência direta entre as operações realizadas nessa estrutura e operações bit-a-bit da linguagem C. Por exemplo, existe uma correspondência entre as operações de teoria dos conjuntos e as operações bit-a-bit. A_B representa o vetor de bits definido pelo conjunto A.

A Ç B = AB  & BB A’ = ~ AB AÈ B = AB  | BB (AÈ B)- (A Ç B) = AB  ^ BB

A – (A Ç B) = (AB  ^ BB ) & AB A- B = AB & ~ BB AÍB = AB & ~ BB == Æ

O jogo do sodoku pode ser descrito da seguinte maneira:

Um tabela quadrada com 9 linhas e 9 colunas é dividida em 9 quadrados menores de 3 x 3 como mostrado na figura abaixo. Em algumas das células estão escritos digitos de 1 a 9. As outras células são vazias. O objetivo é preencher as células vazias com dígitos decimais de 1 a 9, um digito por célula, de tal modo que em cada linha, em cada coluna, e em cada subquadrado 3 x 3, todos os dígitos de 1 a 9 apareçam.

Uma variável do tipo inteira de 32 bits pode ser utilizada para representar conjuntos de até 32 elementos. Vamos definir os conjuntos dos números que aparecem em cada linha, coluna e cada subquadrado.

unsigned int linha[9];

unsigned int coluna[9];

unsigned int subquadrado[9];

Toda vez que um número for encontrado na tabela do jogo Sodoku, vamos adicionar no respectivo conjunto. 

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {       

          if(A[i][j] != 0){

               int ii = i / 3;

                int jj = j / 3;

                linha[i]     |=  1<<(A[i][j]-1);

                coluna[j]    |=  1<<(A[i][j]-1);                   

                subquadrado[3*ii+jj] |=  1<<(A[i][j]-1);

          }   

}

}

Para descobrir quais são os valores possíveis para cada célula (i,j), bastar descobrir quais são os elementos do conjunto representado pelo vetor de bits C:

ii = i / 3;

jj = j / 3;

C = linha[i] | coluna[j] | box[3*ii+jj];

C = ~C & ~(1<<9);