Verstehen der Verwendung von Bit-Vektoren beim Auffinden von eindeutigen Zeichen in einer Zeichenfolge

Question

Ich habe den folgenden Code, der eindeutige Zeichen in einer Zeichenfolge mithilfe von Bitvektoren findet. Wir nehmen an, dass es sich um einen ASCII-Zeichensatz handelt, der nur aus Kleinbuchstaben besteht.

Ich habe eine harte Zeit zu verstehen, die Verwendung von Bit Vektoren unten. Auch nach dem Debugging durch das Programm und nach den Änderungen durchlaufen Variablen nach jeder Schleife.

// assuming that the characters range from a-z 
static boolean isUniqueBitVector(String str) { 
    int checker = 0; 

    for(int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i) - 'a'; 

     if((checker & (1 << val)) > 0) { 
      return false; 
     } else { 
      checker |= (1 << val); 
     } 
    } 
    return true; 
} 

Was ist der Zweck von links die val (int Darstellung jeden Zeichen in string) um 1 Verschieben und verUNDen es mit Prüfer (initialisiert auf 0) und im anderen Block OR-.

Answer 1

checker ist eine 32-Bit-Ganzzahl, von der wir die niedrigsten 26 zuweisen, um ein Flag für jeden Buchstaben a-z zu speichern. Wir können dafür Bits verwenden, weil ein Buchstabe nur einmal nicht eindeutig sein kann.

int val = str.charAt(i) - 'a'; berechnet den Index des Bits, das dem aktuellen Buchstaben entspricht. Hier kommt die Annahme, dass der Eingang nur a-z enthält. val wird eine Zahl zwischen Null und 25 sein.

Im Allgemeinen ist (1 << val) das Bit, das dem ausgewählten Buchstaben entspricht. << ist der Operator der linken Schicht. Es wird verwendet, um 1 zu verschieben, das nur ein einzelnes Bit hat, val Positionen auf der linken Seite. So würde zum Beispiel 1<<3 8 sein. Tatsächlich ist eine Verschiebung nach links gleichbedeutend mit einer Potenz von 2.

(checker & (1 << val)) überprüft, ob das ausgewählte Bit eingeschaltet ist oder nicht. Der Operator & heißt bitweise und. Es kombiniert zwei Zahlen und setzt alle Bits, die in beiden eingeschaltet sind, auf on. Denken Sie daran, dass 1 << val nur ein einzelnes Bit eingeschaltet hat. Die einzige Möglichkeit, das Ergebnis davon und checker wird ungleich Null sein, ist, wenn checker bereits das gleiche Bit eingeschaltet hat. In diesem Fall geben wir false zurück, weil ein Buchstabe wiederholt wurde. Wenn ein neuer Buchstabe gefunden wurde, müssen wir das korrekte Bit in checker einschalten. Dies ist, was checker |= (1 << val); tut. Der bitweise Operator | aktiviert ein Bit im Ergebnis, wenn es in einem der beiden Operanden aktiviert ist. Auch hier hat 1 << val nur ein Bit an. Daher das Ergebnis der oder zu replizieren checker und schalten Sie das ein Bit (ob es schon eingeschaltet war oder nicht).

Alle Operationen, die Sie hier sehen, sind sehr häufige Redewendungen. Hoffentlich hat meine Erklärung Ihnen in gewisser Weise geholfen, denn Sie werden fast sicher sehr ähnliche Dinge in jedem einfachen Bit-Twiddling-Code sehen.