Compare two binary numbers and get the different bits [duplicate]

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.

Interlard

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. – Adenitis

This is called the Hamming Distance. – Masculine

__builtin_popcount (22 ^ 15) = 3 – Bricklaying

Answer 1

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

Phung

Answer 2

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

Godevil

+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. – Masculine

Answer 3

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

Erickericka