Encontrar um padrão de números binários usando shift-direito e bitwise-E?

Question

Eu estou tentando escrever uma função em conjunto que irá detectar se um número mais binário contém um padrão binário menor.

Exemplo:
Does 100111 contém 1001 ?

Quando li este problema eu percebi que eu iria fazer um bit a bit-E com o grande número e seu padrão menor, enquanto deslocando direita (lógico) de cada vez em um loop.

Então, na minha cabeça eu pensei que faria:

100111 AND 1001 = 0  
Shift-right 1  
010011 AND 1001 = 0  
Shift-right 1  
001001 AND 1001 = 1 // Pattern FOUND!  

e repetir este até que o número foi deslocado até que fosse zero ou o e voltou 1.

No entanto, eu acho que deve ter algo confuso porque este é retornar 1 para a maioria das coisas que eu ponho no, na primeira execução do loop. Am I confuso sobre meu uso de E?

Answer 1

O problema é que "resultados parciais" também retorna um valor diferente de zero para o seu E verificar:

100111 AND 001001 = 000001

Portanto, este testes se qualquer dos bits corresponder, mas você quer ter certeza de todas bits são os mesmos. O resultado das e precisa ser igual ao padrão que você está procurando:

x = 100111
if (x AND 1001 == 1001)
  print "found"

Answer 2

Você deve e em seguida, teste contra o padrão de pesquisa:

if ((TestPattern & SearchPattern) == SearchPattern)
{
   // then match
}

(onde & representa AND bit a bit)

Answer 3

Bitwise e não funciona da forma esperada (a julgar a partir das amostras e ignorando a notação que parece sugerir que você está usando bit a bit E como a lógica AND dos bits). E leva apenas os bits que estão definidos para 1 "em conta". Por exemplo 1111 AND 1001 == 1001.

Você precisa usar XOR e comparar com 0 para o jogo (lembre-se a mascarar os bits que você não está comparando a partir do resultado). No seu exemplo for encontrada uma correspondência quando (N ^ 1001) e 1111 == 0000

Answer 4

A fim de certificar-se de que ambos os 0 e 1 bits corresponder ao seu padrão de busca, você precisa fazer algo como isto:

if ((InputPattern AND SearchMask) == SearchPattern)
{
    // then match
}

O SearchMask deve ser todos os bits 1, de comprimento igual ao seu searchPattern. Por exemplo, você poderia ter SearchMask == 1111, SearchPattern == 1001.