Suchen Sie ein Muster von Binärzahlen mit Shift-rechts und bitweise-UND?

Question

Ich versuche eine Funktion in Assembly zu schreiben, die erkennt, ob eine längere Binärzahl ein kleineres Binärmuster enthält.

Beispiel:
Hat enthalten ?

Als ich dieses Problem gelesen habe, dachte ich, dass ich ein bitweises UND mit der großen Zahl und seinem kleineren Muster machen würde, während ich jedes Mal in einer Schleife nach rechts (logisch) wechsle.

in meinem Kopf Also, ich dachte, es tun würde:

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

und wiederholen Sie dies, bis entweder die Zahl verschoben wurde, bis er Null war oder das AND 1 zurück

Aber ich denke, ich muss etwas verwirrt haben, weil dies 1 für die meisten Dinge, die ich eingefügt habe, beim ersten Durchlauf der Schleife zurückgibt. Bin ich verwirrt über meine Verwendung von AND?

Answer 1

Das Problem ist, dass "teilweise Übereinstimmungen" auch einen Nicht-Null-Wert für Ihre Rückkehr und überprüfen:

100111 AND 001001 = 000001 

So dies testet, wenn beliebig der Bits übereinstimmen, aber Sie sicherstellen möchten, dass alle Bits identisch sind. Das Ergebnis der UND muss das Muster gleich sein, das Sie suchen:

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

Answer 2

Sie sollten UND und dann Test gegen das Suchmuster:

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

(wo & repräsentiert bitweise AND)

Answer 3

bitweise UND funktioniert nicht wie erwartet (von den Proben zu urteilen und ignoriert die Notation, die darauf hindeutet, dass Sie bitweises UND als logisches UND von Bits verwenden). UND berücksichtigt nur die Bits, die auf "1" gesetzt sind. ZB 1111 AND 1001 == 1001.

Sie müssen XOR verwenden und mit 0 vergleichen, um eine Übereinstimmung zu finden (erinnern Sie sich an die Maske, die Bits, die Sie nicht vom Ergebnis vergleichen). In Ihrem Beispiel wird eine Übereinstimmung gefunden, wenn (N^1001) & 1111 == 0000

Answer 4

Um sicher zu stellen, dass sowohl die Bits 0 und 1 Ihr Suchmuster entsprechen, müssen Sie so etwas wie dies zu tun:

Die SearchMask sollte alle 1 Bits sein, von einer Länge gleich Ihrem SearchPattern. Zum Beispiel könnten Sie SearchMask == 1111, SearchPattern == 1001 haben.