Compare two binary numbers and get the different bits

Question

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

I want to write a program to get the number of 1's bit in comparing two numbers.if I compare the bits between any two numbers to find where the binary numbers are different in the 1's and 0's. in other words Exclusive OR (XOR) relationship.

like if 22 (which has 10110 binary)and compare it with 15 (which has 01111 binary)

the first one 10110

the second one 01111

the result 11001

and the answer would be 25 but what I want to get is 3 where there is three 1's and 0's that are different.

Some CPUs have a special hardware instruction for population count. It'd be interesting to know if compilers know about this and can be made to emit the relevant code. — Kerrek SB, Mar 31 '12 at 09:46
This is called the [Hamming Distance](http://en.wikipedia.org/wiki/Hamming_Distance). — Potatoswatter, Mar 31 '12 at 11:03

score 7 · Answer 1 · answered Mar 31 '12 at 09:29

7

Hrmmm, the first non-recursive idea that comes to mind is:

int a = ...;
int b = ...;
int x = a ^ b;

int count;

for (int i = 0; i < 32; ++i) {
    if (x & (1 << i)) {
        ++count;
    }
}

answered Mar 31 '12 at 09:29

Corbin

33,060
6
68
78

score 3 · Answer 2 · answered Mar 31 '12 at 09:29

3

std::bitset::count should do what you're looking for:

http://www.cplusplus.com/reference/stl/bitset/count/

http://en.cppreference.com/w/cpp/utility/bitset/count

answered Mar 31 '12 at 09:29

Ben Cottrell

5,741
1
27
34

2

+1. It's important to use the library function if your program spends a lot of time doing this, because most microprocessors have a dedicated "population count" instruction that is difficult to portably access otherwise. Also note that `bitset` supports XOR and conversion to and from `unsigned long` numbers. – Potatoswatter Mar 31 '12 at 11:05

Bartosz Moczulski · Answer 3 · 2012-03-31T09:37:54.313

0

This would be the easiest approach:

int count_bits(int a)
{
    int mask;
    int count = 0;
    for (mask = 1; mask; mask <<= 1)
    {
        if (mask & a) ++count;
    }
    return count;
}

If you want something more fancy take a look here: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

edited Mar 31 '12 at 09:37

answered Mar 31 '12 at 09:32

Bartosz Moczulski

1,209
9
18

Compare two binary numbers and get the different bits

3 Answers3