Trouvez un motif de nombres binaires en utilisant shift-right et bitwise-AND?

Question

J'essaie d'écrire une fonction dans l'assembly qui détectera si un nombre binaire plus long contient un motif binaire plus petit.

Exemple:
100111 contient-il 1001 ?

Quand j'ai lu ce problème, j'ai pensé que je ferais un bitwise-AND avec le grand nombre et son motif plus petit en décalant vers la droite (logique) à chaque fois dans une boucle.

Donc, dans ma tête, je pensais que ça irait:

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

et répétez cette opération jusqu'à ce que le numéro soit décalé jusqu'à ce qu'il soit égal à zéro ou que l'AND ait renvoyé 1.

Cependant, je pense que je dois avoir quelque chose de confus, car il retourne 1 pour la plupart des choses que j'ai insérées, lors de la première exécution de la boucle. Suis-je confus sur mon utilisation de AND?

Answer 1

Le problème est que " correspondances partielles " renvoie également une valeur non nulle pour votre chèque AND:

100111 AND 001001 = 000001

Cela teste donc si un des bits correspond, mais vous voulez vous assurer que tous sont identiques. Le résultat de AND doit être égal au modèle recherché:

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

Answer 2

Vous devriez AND, puis tester par rapport au modèle de recherche:

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

(où & amp; représente bitwise AND )

Answer 3

ET au niveau des bits AND ne fonctionne pas comme prévu (à en juger par les exemples et en ignorant la notation qui semble suggérer que vous utilisez AND au niveau des bits en tant que AND logique des bits). AND ne prend en compte que les bits définis sur 1 "." 11g ET 1001 == 1001.

Vous devez utiliser XOR et comparer à 0 pour la correspondance (souvenez-vous du masque les bits que vous ne comparez pas du résultat). Dans votre exemple, une correspondance est trouvée lorsque (N ^ 1001) & amp; 1111 == 0000

Answer 4

Pour vous assurer que les bits 0 et 1 correspondent à votre modèle de recherche, vous devez procéder comme suit:

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

Le SearchMask doit comporter 1 bit, d’une longueur égale à votre SearchPattern. Par exemple, vous pourriez avoir SearchMask == 1111, SearchPattern == 1001 .