Wie konnte ich testen, ob zwei Bitmuster in beliebigen N Bits unterscheidet (Position spielt keine Rolle)

StackOverflow https://stackoverflow.com/questions/1502452

  •  19-09-2019
  •  | 
  •  

Frage

Lassen Sie uns sagen, dass ich dieses Bit Feldwert haben: 10101001

Wie würde ich testen, ob ein anderer Wert in irgendwelchen n Bits unterscheidet. Ohne zu bedenken die Positionen?

Beispiel: 

10101001
10101011 --> 1 bit different 

10101001
10111001 --> 1 bit different

10101001
01101001 --> 2 bits different

10101001
00101011 --> 2 bits different

Ich brauche eine Menge dieser Vergleiche zu machen, so dass ich in erster Linie für die Perfomance der Suche bin, aber jeder Hinweis ist sehr willkommen.

War es hilfreich?

Lösung

Nehmen Sie die XOR der beiden Felder und eine Bevölkerungszahl des Ergebnisses tun.

Andere Tipps

Wenn Sie die zwei Werte miteinander XOR, Sie sind mit den Bits nur links, die anders sind.

Sie müssen dann nur die Bits zählen, die noch 1 sind, und Sie haben Ihre Antwort

in c: 

 unsigned char val1=12;
 unsigned char val2=123;
 unsigned char xored = val1 ^ val2;
 int i;
 int numBits=0;
 for(i=0; i<8; i++)
 {
      if(xored&1) numBits++;
      xored>>=1;
 }

obwohl es wahrscheinlich schnelle Möglichkeiten, um die Bits in einem Byte zu zählen (Sie könnte zum Beispiel eine LookupTable für 256 Werte verwenden)

Genau wie alle anderen auch gesagt, verwenden XOR, um zu bestimmen, was anders ist, und dann ein verwenden diese Algorithmen zählen .

Dies wird die Bit-Differenz zwischen den Werten und zählt die Bits drei auf einmal: 

public static int BitDifference(int a, int b) {
   int cnt = 0, bits = a ^ b;
   while (bits != 0) {
      cnt += (0xE994 >> ((bits & 7) << 1)) & 3;
      bits >>= 3;
   }
   return cnt;
}

die Zahlen XOR, dann wird das Problem darum, die 1s im Ergebnis zu zählen.

In Java: 

Integer.bitCount(a ^ b)

Es wird ein Vergleich mit XOR durchgeführt, wie andere bereits beantwortet.

Zählen kann auf verschiedene Arten durchgeführt werden:

  • Verschiebung nach links und zusätzlich.
  • Nachschlagen in einer Tabelle.
  • Logik Formeln, die Sie mit Karnaugh finden Maps .
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top