Tutorial :Find count of overlapping 1 bits



Question:

I'm trying to find the number of overlapping 1 bits between 2 given numbers.

For example, given 5 and 6:

5 // 101  6 // 110  

There is 1 overlapping 1 bit (the first bit)

I have following code

#include <iostream>  using namespace std;    int main() {      int a,b;      int count = 0;      cin >> a >> b;      while (a & b != 0) {          count++;          a >>= 1;          b >>= 1;      }      cout << count << endl;        return 0;  }  

But when I entered 335 and 123 it returned 7 but I think it is not correct

Can someone see a problem with my code?


Solution:1

The problem is that you're just printing out the number of times any of the bits match, as you lop off the least significant bit for each iteration (which will at max be the number of bits set for the smaller number). You're comparing all bits of [a] BITWISE AND [b] each iteration. You could rectify this by masking with 1: a & b & 1, so that while you're shift thing bits rightward each time, you're only checking if the least significant bit is being checked:

while (a && b){      count += a & b & 1;      a>>=1;      b>>=1;  }  


Solution:2

Your existing algorithm counts each bit as long as any bit in the remaining bits to test matches; since 123 and 335 have a common MSB, it's true as long as either number is non-zero. 123 is the smaller with 7 bits, so it's true 7 times until that number is completely processed. As an extreme case, 128 (10000000) and 255 (11111111) would return 8 with your method, even though it's actually 1.

You want to AND the two numbers together to start with and then count the number of 1s in that result


Solution:3

You want to count the number of bits that are set. Instead, your code is sort of computing the binary logarithm.

Only increment the count if the lowest order bit is set.

for (int c = a & b; c != 0; c >>= 1) {    if (c & 1)      ++count;  }  


Solution:4

Slightly shorter form:

int countCommonBits(int a,int b) {          int n = 0;      for (unsigned v = (unsigned)(a & b); v; v >>= 1) {          n += 1 & v;      }      return n;  }  

If you know both numbers are positive, you can omit the use of the unsigned type. Note when using "int" that sign extension on a right shift of a negative number would give you a bit of an overcount (i.e. an infinite loop).

Much later... Reviewing an old answer, came across this. The current "accepted" answer is 1) inefficient, and 2) an infinite loop if the numbers are negative. FWIW.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »