Number of Differing Bits

Given two integers count the number of positions where their bit representation differs. A simple approach is to use their binary representation and compare them. They can also be compared on the fly.

Approach : XOR

Let’s take a look at the truth table of XOR operation:

A	B	Y = A ^ B
0	0	0
0	1	1
1	0	1
1	1	1

It is evident that XOR operation gives 1 if the two bits are different (see row 2 and 3). So, the set bits in A ^ B will be the ones where the binary representation of A and B differ.

For example,

A = 19 => 10011
B = 10 => 01010
--------------------
A ^ B => 11001

Thus, the number of set bits in A ^ B will give the desired answer. We can useBrian-Kernighan methodto count the number of set bits.

C++ code:

#include<iostream>
using namespace std;

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // clear the right-most bit
        ++count;
    }
    return count;
}

int countDifferntBits(int a, int b) {
    return countSetBits(a ^ b);
}

int main() {
    cout << "Number of different bits of " << 19 << " and " << 10 << " is " << countDifferntBits(19, 10) << "\n";
    return 0;
}

Python code:

def count_set_bits(n):
    count = 0
    while n > 0:
        n = n & (n - 1) # clear the right most bit
        count += 1
    return count

def count_different_bits(a, b):
    return count_set_bits(a ^ b)

if __name__ == ' __main__':
    print('Number of different bits of', 19, 'and', 10, 'is', count_different_bits(19, 10))

Time Complexity: O(log(min(a, b)))
Space Complexity: O(1)

Exercise: Code the naive solution.

Blog

Number of Differing Bits

Ayan Banerjee

Approach : XOR

Join Our Newsletter. No Spam, Only the good stuff.

Related