How could I test if two bit patterns differs in any N bits (position doesn't matter)

Question

Let's say i have this bit field value: 10101001

How would i test if any other value differs in any n bits. Without considering the positions?

Example:

10101001
10101011 --> 1 bit different 

10101001
10111001 --> 1 bit different

10101001
01101001 --> 2 bits different

10101001
00101011 --> 2 bits different

I need to make a lot of this comparisons so i'm primarily looking for perfomance but any hint is very welcome.

Answer 1

Take the XOR of the two fields and do a population count of the result.

Answer 2

if you XOR the 2 values together, you are left only with the bits that are different.

You then only need to count the bits which are still 1 and you have your answer

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

although there are probably faster ways to count the bits in a byte (you could for instance use a lookuptable for 256 values)

Answer 3

XOR the numbers, then the problem becomes a matter of counting the 1s in the result.

Answer 4

Just like everybody else said, use XOR to determine what's different and then use one of these algorithms to count.

Answer 5

Comparison is performed with XOR, as others already answered.

counting can be performed in several ways:

• shift left and addition.
• lookup in a table.
• logic formulas that you can find with Karnaugh maps.

Answer 6

This gets the bit difference between the values and counts the bits three at a time:

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 7

In Java:

Integer.bitCount(a ^ b)