0

I have a problem wherein I need to find the number of matching bits (from left to right) between two integers

Inputs: 2 Variable A and B to store my decimal numbers

Output: Numbers of bits in A and B that match (starting from the left)

Some Examples:

A = 3 and B = 2, A and B bits match up to 7 bits from the left bit

A = 3 and B = 40, A and B bits match up to 7 bits from the left bit.

How can I do that using bitwise operation (AND,OR,XOR)?

Thanks

Joe Elleson
  • 1,353
  • 10
  • 16
The Mr. Totardo
  • 1,119
  • 2
  • 10
  • 11

3 Answers3

2

XOR the two together (to produce a number which has all zeroes from the left until the first non matching element), then shift the result right until it equals 0. Subtract this from the bit length of the integers you are dealing with (e.g., you seem to be implying 8 bits).

pseudocode:

int matchingBits(A, B) {
    result = A XOR B
    int shifts = 0
    while (result != 0) {
        result = result >> 1 (Shift right the result by 1)
        shifts++
    }
    return integer_bit_length - shifts
}
Joe Elleson
  • 1,353
  • 10
  • 16
1

Do (A XNOR B) to find the matching digits:

10101010
01001011
--XNOR--
00011101

Then use the hamming algorithm to count the ones: Count number of 1's in binary representation

(btw: xnor is !xor)

Community
  • 1
  • 1
Efrain
  • 3,248
  • 4
  • 34
  • 61
  • This counts the total number of matching bits, he wants the number of matching bits from the left until the first mismatch – Joe Elleson Apr 19 '13 at 11:25
0

try this may be it will work

int matchingBitsCount(val1,val2)
{
  int i , cnt = 0;
  for(i=7;i>=0;i--)
 {
       if(((1<<i)&a)^((1<<i)&b))==0)  //left shifted for starting from left side and then XOR
       {
       cnt++;
       }
      else
      {
        break;
      }
   }
 }

i take val1 and val 2 as char if you want to check for int then just take i=31

umang2203
  • 78
  • 5