Come potrei verificare se due schemi di bit differisce N bit (posizione non importa)

Question

Diciamo che ho un po ' il valore di campo: 10101001

Come faccio a verificare se qualsiasi altro valore differisce n bit.Senza considerare le posizioni?

Esempio:

10101001
10101011 --> 1 bit different 

10101001
10111001 --> 1 bit different

10101001
01101001 --> 2 bits different

10101001
00101011 --> 2 bits different

Ho bisogno di fare un sacco di questo confronto così sono principalmente alla ricerca per la prestazione, ma le eventuali suggerimento è il benvenuto.

Answer 1

Prendere la XOR dei due campi e fare un conteggio della popolazione del risultato.

Answer 2

se si XOR 2 valori insieme, si sono lasciati solo con i bit che sono diversi.

È quindi solo bisogno di contare i pezzi che sono ancora 1 e hai la tua risposta

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;
 }

anche se ci sono probabilmente i modi più veloci per contare i bit in un byte (si potrebbe ad esempio utilizzare un lookuptable per 256 valori)

Answer 3

Proprio come tutti gli altri, ha detto, usare XOR per determinare ciò che è diverso e quindi utilizzare uno di questi algoritmi per contare .

Answer 4

Questo ottiene la differenza po 'tra i valori e conta i bit tre alla volta:

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;
}

Answer 5

XOR i numeri, allora il problema diventa una questione di contare i 1s nel risultato.

Answer 6

In Java:

Integer.bitCount(a ^ b)

Answer 7

Il confronto è effettuato con XOR, come altri già risposto.

conteggio può essere effettuato in diversi modi:

• spostamento a sinistra e oltre.
• ricerca in una tabella.
• formule logiche che si possono trovare con Karnaugh mappe .