9 janeiro, 2011 7 Comentários AUTOR: elemarjr CATEGORIAS: Sem categoria Tags:,

The Magic Bitscan

Tempo de leitura: 2 minutos

Olá pessoal, tudo certo?

O post de hoje é uma diversão! Se você não trabalha com sistemas de alto-desempenho, que manipulem estruturas de dados fundamentadas em mapas de bits, provavelmente não encontrará aplicação prática para o conceito que demonstrarei hoje.

Por outro lado, se gosta de computação, encontrará aqui um “prato cheio”, instrutivo e divertido.

Hoje vou apresentar um método “mágico” para descoberta do índice do bit menos significativo (LSB) de um determinado número. O método que será apresentado trabalha com a construção de uma hashtable e pela definição de uma hash function realmente rápida.

O método que apresento está fundamentado no trabalho do Professor Pradyumma Kannan.

O que é Bitscan? Quando utilizo?

Bitscan é o processo do MSB ou LSB de um determinado número binário. É um processo utilizado com frequência quando utilizamos números binários como estrutura de dados.

Se você está acompanhando a série que estou escrevendo sobre Xadrez, perceberá que utilizo uma estrutura chamada Bitboard (um inteiro não sinalizado, de 64 bits) para representar a ocupação do tabuleiro (entre outras coisas). Lá, processos de bitscan são muito importantes.

O que é LSB?

LSB é indicação do bit menos significativo de um determinado número. Considere o número 44 (binário 101100), seu bit menos significativo [ligado] será o terceiro (101100). Compreendido?

Isolando o LSB

Uma operação útil, quando trabalhando com registros binários, é a capacidade de isolar o LSB. Ou seja, gerar um novo registro apenas com esse bit ligado.

Voltemos ao exemplo do número 44. Sua representação em binário, como já mencionado é 101100. A representação do LSB isolado seria 000100 (4 em decimal). Mas, como obter esse número rapidamente? O processo é mais simples do que possa parecer:

Dado um número X (no nosso exemplo 44, binário 101100):

  1. Obtemos a representação NOT de X (em C#, not = ~X). O “not” de 44 seria, 010011;
  2. Ligamos o primeiro bit, menos significativo desligado, obtendo a máscara para o LSB ( maskLSB = not + 1 // 010111);
  3. Executamos um AND entre X e a máscara LSB (isolatedLSB = X & maskLSB). O resultante, será o LSB “isolado”. Em nosso exemplo, 000100.

Resumindo, o LSB isolado para X é (X & (~X + 1)).

Por que Magic?

A técnica apresentada nesse post é conhecida como “Magic Bitscan” porque utiliza uma técnica de hashing chamada “Magic Hashing Function”. Dada uma determinada tabela hash (criaremos uma “no braço”), com 64 entradas, o índice é computado por uma Hash Function com a seguinte estrutura:

index = (key * magic) >> 58

Onde:

  1. key é o LSB isolado;
  2. magic é uma chave computada [vemos mais tarde]
  3. deslocamento de 58 é o número entradas na hash menos o tamanho (em bits) das chaves diretas para a Hash (64 – 6).

Magic LSB Bitscan para números de 64 bits

Vejamos o conceito apresentado em um método otimizado para computar o LSBBitscan para números de 64 bits. Eis o método:

1 const ulong magic64 = 0x07EDD5E59A4E28C2ul; 2 static int LSBBitscan64(ulong x) 3 { 4 if (x == 0) return -1; 5 ulong key = (x & (~x + 1)); 6 return index64[(key * magic64) >> 58]; 7 } 8 9 static int[] index64 = new int[64]; 10 static void InitializeIndex64() 11 { 12 ulong bit = 1; 13 int i = 0; 14 do 15 { 16 index64[(bit * magic64) >> 58] = i; 17 i++; 18 bit <<= 1; 19 } while (bit != 0); 20 }

Os dois métodos aplicam o conceito mostrado acima. Observe:

  • Na linha 1, apresento o número mágico computado para bitscans em números de 64bits.
  • O método LSBBitscan64 recebe um número de 64 bits (ulong) e devolve o índice do LSB (-1 se não houver nenhum bit ligado);
  • A hashtable é computado pelo método InitializeIndex. Observe que gero uma representação para cada LSB isolado em 64 bits, chego no índice na hash e armazendo o índice do LSB.

Esse método é muito rápido. O mistério é: De onde saiu 0x07EDD5E59A4E28C2ul? Por hora, basta dizer que o número mágico para 8 bits seria 0x3A

Calculando o número mágico (na mão)

A primeira coisa que precisa entender é que um número de 64 bits pode possuir 64 posições possíveis para o LSB (0..63), Essas possibilidades podem ser armazenadas em um vetor de 64 posições. Com índices binários que vão de 000000 (0 decimal) até 111111 (63 decimal). Ou seja, 6 bits. Já um número de 8 bits, tem oito possibilidades que vão de 000 (0 decimal) até 111 (7 decimal). Assim, para um número de 8 bits, precisamos de chaves de apenas 3 bits.

Por hora, o código e a chave mágica  que apresento podem parecer bastante "misteriosos”. Vamos simplificar um pouco a coisa!

Comecemos por simplificar um pouco a “multiplicação”. Considere:

  • Se houver apenas um bit ligado em um número, ele poderá ser sempre representado como uma potência de 2
    • 1 (1 binário) = 20
    • 2 (10 binário) = 21
    • 4 (100 binário) = 22
    • 8 (1000 binário) = 23
    • 16 (10000 binário) = 24
  • Também podemos ver que b*2n corresponde a b << n (o que é bem mais leve)
    • 010110 (binário) * 10 (binário) = 101100 (binário) = 010110 (binário) << 1 (decimal) ;
    • 001101 (binário) * 100 (binário) = 110100 (binário) = 001101 (binário) << 2 (decimal);

O próximo passo que precisa ser observado é que o shift para direita (>> 8 para números de 64 bits ou >> 3 para números de 3 bits) desloca o índice para o vetor hash para a base.

Para número de 8 bits, precisamos de um magic de 8 bits. Consideremos esse número “graficamente” como abcdefgh. Pela lógica que estamos aplicando, (key * magic) >> 5 teríamos que:

  • para a chave 00000001, o índice para o vetor hash seria abc;
  • para a chave 00000010, o índice seria bcd;
  • para a chave 00000100, o índice seria cde;
  • para a chave 00001000, o índice seria def;
  • para a chave 00010000, o índice seria efg;
  • para a chave 00100000, o índice seria fgh;
  • para a chave 01000000, o índice seria gh0;
  • para a chave 10000000, o índice seria h00;

Certo?

Para gerar o valor magic, basta apenas termos certeza que será gerado apenas um índice único (três bits) para cada key (LSB isolado). Para fazer isso, basta aplicar alguma tentativa e erro. Considere

|abcdefgh| 1 | 0|00 // 0 em h 2 | 00|0 // 0 em g - colisão com 1 3 | 10|0 // 1 em g 4 | 010| // 0 em f 5 | 001 | // 0 em e - todas as próximas var. colidem 6 | 000 | // 0 em d - colisão com 1 7 | 100 | // 1 em d - colisão com 3 8 | 101 | // 1 em e 9 | 010 | // 0 em d - colisão com 4 10| 110 | // 1 em d 11| 011 | // 0 em c - todas as próximas var. colidem 12| 001 | // 0 em b - todas as próximas var. colidem 13|000 | // 0 em a - colisão com 1 14|100 | // 1 em a - colisão com 3 15| 101 | // 1 em b - colisão com 8 16| 111 | // 1 em c 17| 011 | // 0 em b 18|001 | // 0 em a

Juntando os bits, com um OR para todas as linhas que representam não-colisões, temos:

|abcdefgh| 1 | 0|00 // 0 em h 3 | 10|0 // 1 em g 4 | 010| // 0 em f 8 | 101 | // 1 em e 10| 110 | // 1 em d 16| 111 | // 1 em c 17| 011 | // 0 em b 18|001 | // 0 em a OR|00111010| = 0x3A (58 em decimal)

E temos nossa magic para números de 8 bits.

Calculando o número mágico (com ajuda de algum código)

Chegar no número mágico é chato. Imagine se tentar calcular o número mágico para números de 64 bits! Por isso, segue algum código para apoiar essa “conta”.

const int KEYSCOUNT = 8; //64; const int KEYBITSCOUNT = 3; // 6; static int[] bits = new int[KEYSCOUNT]; static bool[] usedCombinations = new bool[KEYSCOUNT]; static bool ComputeBit(int index) { if (index == KEYSCOUNT) return true; bits[index] = 0; if (usedCombinations[GetCombination(index)]) { bits[index] = 1; if (usedCombinations[GetCombination(index)]) { return false; } } usedCombinations[GetCombination(index)] = true; if (!ComputeBit(index + 1)) { usedCombinations[GetCombination(index)] = false; if (bits[index] == 0) { bits[index] = 1; if (usedCombinations[GetCombination(index)]) return false; return ComputeBit(index + 1); } } return true; } static ulong ComputeMagic() { ulong product = 0; for (int i = 0; i < bits.Length; i++ ) product += (ulong)bits[i] << i; return product; } static int GetCombination(int index) { var product = 0; for (int i = 0; i < KEYBITSCOUNT; i++) { var k = index - i; if (k < 0) break; product += bits[k] << (KEYBITSCOUNT - (i + 1)); } return product; }

Chamando ComputeBit( 0 ), Seguido de Console.WriteLine(“{0:X}”, ComputeMagic()); obtemos 3A

Mudando KEYSCOUNT para 64 e KEYBITSCOUNT para 6, obtemos 7EDD5E59A4E28C2 (número da sorte do @juanplopes)

Por hoje, era isso!

7 Comentários

  1. Leandro Daniel 6 anos ago says:

    Não conhecia a técnica "Magic Bitscan", muito show.

    Há muito tempo, conversando com um colega, ele me explicou que muitos filtros utilizados em tratamento de imagens podem fazer uso dessas técnicas de operações com bits, pois é bem rápido. Você já fez alguma coisa do tipo?

    Abraços e parabéns pelo post!

    Leandro Daniel

    Responder
    • elemarjr 6 anos ago says:

      Já sim ... posso escrever algo sobre isso por aqui nos próximos dias
      😀

      Responder
  2. Fernando 6 anos ago says:

    O bit menos significativo não é o primeiro, da direita para a esquerda? http://es.wikipedia.org/wiki/Bit_menos_significativo

    Responder
    • elemarjr 6 anos ago says:

      Nesse post, considero LSB o bit ligado mais a direita.

      Responder

Trackbacks para este post

  1. Tweets that mention The Magic Bitscan « Elemar DEV -- Topsy.com
  2. Encontrando o “Bit menos significativo ligado” em F# (usando Magic Bitscan) | Elemar DEV
  3. Encontrando o "Bit menos significativo ligado" em F# (usando Magic Bitscan) | Elemar JR