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?

335 in binary = 101001111; 123 in binary = 001111011. Looks like 4 to me. — Dave Jarvis, Jul 13 '10 at 21:01
Your algorithm is incorrect - you just need to AND the two values and then do a population count on the result. — Paul R, Jul 13 '10 at 21:28
I think it's worth pointing out that this question is essentially asking how to calculate `hammingWeight(a & b)`. There are some good answers how to calculate Hamming Weight here: http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer — clstrfsck, Apr 21 '13 at 01:21

score 2 · Answer 1 · answered Jul 13 '10 at 21:01

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

Marc Bollinger · Accepted Answer · 2010-07-13T22:15:48.190

2

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

edited Jul 13 '10 at 22:15

answered Jul 13 '10 at 21:02

Marc Bollinger

3,109
2
27
32

The first sentence isn't strictly true; 85 (01010101) and 170 (10101010) would output 0, as they have none in common. He's printing the offset of the most significant matching bit – Michael Mrozek Jul 13 '10 at 21:26

score 1 · Answer 3 · answered Jul 13 '10 at 21:04

1

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

answered Jul 13 '10 at 21:04

erickson

265,237
58
395
493

I like Marcs answer better for clarity, but this one is better for fewer operations (I would like this version done as the equivalent while loop, but that is personal preference). – Dolphin Jul 14 '10 at 14:17

Preston L. Bannister · Answer 4 · 2014-10-22T15:54:21.010

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.

Find count of overlapping 1 bits

4 Answers4