Finden Sie ein Muster von binären Zahlen mit Shift-rechts und bitweise UND-Verknüpfung?

Question

Ich versuche, eine Funktion bei der Montage zu schreiben, die erkennt, wenn eine längere binäre Zahl ein kleineres binären Muster enthält.

Beispiel:
Ist 100111 enthalten 1001

Wenn ich dieses Problem habe ich gelesen, dachte, dass ich eine bitweise UND-Verknüpfung tun würde mit der großen Zahl und ihre kleineren Muster während rechts (logisches) jedes Mal in einer Schleife zu verschieben.

Also, in meinem Kopf dachte ich, 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 wurde die Zahl verschoben, bis es Null war oder das UND ergab 1.

Aber ich denke, ich verwirrt etwas haben muss, weil diese 1 für die meisten Dinge zurückkehr ich in setzen, auf dem ersten Lauf der Schleife. Bin ich verwirrt auf 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 diese Tests, wenn jeder der Bits passen, aber Sie wollen sicherstellen, dass alle Bits sind gleich. Das Ergebnis der UND muss gleich das Muster, 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
}

(wobei & repräsentiert bitweise AND)

Answer 3

bitweise UND funktioniert nicht wie erwartet (von den Proben zu urteilen und die Schreibweise zu ignorieren, die Sie verwenden, bitweise AND als logische UND von Bits scheint darauf hinzudeuten). Und nimmt nur die Bits, die 1 „zu berücksichtigen“ gesetzt sind. Z. B 1111 AND 1001 == 1001.

Sie müssen XOR verwenden und gegen 0 für Spiel vergleichen (Sie erinnern sich die Bits, die die Maske, die Sie nicht aus dem Ergebnis vergleichen). In Ihrem Beispiel wird eine Übereinstimmung gefunden, wenn (N ^ 1001) und 1111 == 0000

Answer 4

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

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

Die SearchMask sollten alle 1 Bits sein, mit einer Länge gleich Ihre search. Zum Beispiel könnten Sie SearchMask == 1111, SearchPattern == 1001 haben.