Ich bin wirklich schlecht in Mathe und möchte eine binäre Operation durchführen

Question

Ich habe das folgende Code:

    public void AddHash( int val )
    {
        m_Hash ^= (val & 0x3FFFFFF);
        m_Hash ^= (val >> 26) & 0x3F;
    }

Ich möchte sehr wissen, was zum Teufel es tut, aber ich wäre zufrieden, zu wissen, wie man a baut bool HasHash( int val ) Das sagt mir, ob m_hash diese Nummer hat oder nicht ...

etwas wie das?

    public bool HasHash( int val )
    {
        return (m_Hash & val) == 0;
    }

Answer 1

Bearbeiten Sie, um den Fehler zu beheben, den @Schnaader gefunden hat: Was es macht? Dieser Code wahrscheinlich will rotieren val links (im Uhrzeigersinn) um 6 Bit (Bearbeiten: Nicht das Produkt, wie ich bereits gesagt hatte) - Das XOR- von diesem gedrehten Wert und dem aktuellen Wert von m_Hash eine neue liefern m_Hash. Das neue m_Hash wird beim nächsten Mal verwendet AddHash( ) wird genannt.

Der so geschriebene Code hat jedoch einen Fehler: Er dreht sich nur um 6 Bits von hoher Bestellung von val links, die niedrigeren Bestellungen 26 Bit von in Position lassen val. Der Code XORS dann drei Werte miteinander zusammen:

1. die neuen 6-Bit von niedriger Ordnung (alte hohe Ordnung) von 6 Bits von val;
2. das ursprüngliche, ungeschichtete 26-Bit von niedriger Ordnung von val; und
3. der aktuelle Wert von m_Hash

das Ergebnis lassen m_Hash.

Wie macht es das? Sie können es einfach abbilden und nachahmen:

1. val & 0x3FFFFFF bedeutet, die 26 Bit von niedriger Ordnung zu extrahieren val.

2. xor diese 26 Bit mit dem aktuellen Wert von m_Hash

3. Jetzt verschieben val rechts so, dass die 26-Bit mit niedriger Ordnung das Ende niedriger Ordnung fallen, sodass früher 6 Bit von hoher Ordnung waren val in der niedrigen Ordnung 6 Bit von val.

4. Maske mit 0x3f Nur die 6-Ordnung mit 6 Bits zu extrahieren (falls einige fremde Bits in den Teil der hohen Ordnung von verschoben wurden val).
5. xor diese 6 Bit mit dem aktuellen Wert von niedriger Ordnung m_Hash das Neue geben m_Hash.

Sie wissen, dass rotierende und exklusive Erhöhungen gemeinsame Operationen bei der Berechnung eines Hashs sind.

BEARBEITEN: @Schnaader wies auf den Fehler im ursprünglichen Code hin: Dieser Code hat vergessen, das andere Bein des Drehens zu erledigen: Verschiebung der 26-Bit-Low-Stahl-26-Bits von 6. Um dies zu beheben, sollte der Code so etwas wie folgt:

public void AddHash( int val )
{
  m_Hash ^= ((val & 0x3FFFFFF) << 6);
  m_Hash ^= (val >> 26) & 0x3F;
}

In Bezug auf dein HasHash( ) Funktion: Sie sollten dieses Sprichwort wissen

return (m_Hash & val) == 0;

Wird unter vielen Bedingungen wahr zurückkehren, einschließlich einiger, die Sie vielleicht nicht wollen. Zum Beispiel wird die Funktion true zurückgegeben, wenn m_Hash == 0xC0 und val == 0x03.

Answer 2

Was der Code tut

Es dauert die letzten 26 Teile von val und kombiniert es mit m_Hash Verwendung Xor. Danach kombiniert es dies mit den ersten 6 Bits von val. Eine Ganzzahl mit 32 Bitlänge wird also auf 26 Bit reduziert. Laut dem Pigeonhole -Prinzip, das ist nicht reversibel.

Hashash -Funktion

Sie werden also nicht in der Lage sein, eine zu erstellen HasHash Funktion auch, wenn Sie nur angerufen haben AddHash nur einmal, weil mehrere Eingabewerte in val wird dazu führen m_hash Wert.