You are given 2 integers, and you need to return the count at which the bits are different in their binary form.
Consider 8 and 1
As highlighted in the image, there are 2 positions where the bits are different. Hence output should be 2.
We shall solve this by bit manipulation.
Before solving the problem, we need to understand 2 concepts
- XOR
- Brian Kernighan’s Algorithm
- XOR
The truth table of xor is as below:
As you can see that XOR returns true if 2 bits are different. When 2 bits are same it will return 0. This is what we need for our solution.
Now that when we XOR 2 numbers, we get numbers of set bits that are different in their binary form.
Now we need to calculate/count the number of set bits.
This can be achieved by using Brian Kernighan’s Algorithm.
This algorithm works on below 2 steps:
- Subtract 1 from the number will flip all the rightmost set bit.
- and using bitwise & operator with (n) &(n-1) will remove the rightmost set bit from n.
i.e consider 10 in binary is 1 0 1 0
subtract -1
Result = 1001 i.e 9.
When we do (1010 & 1001) we get 1000.
Similarly, we continue like this till we get the count of set bits of number 10.
Method 2:
We can also solve this problem with help of library function available in C++ as below:
bitset<32>(x^y).count();
Solution in C++
#include<iostream> using namespace std; int hamming_distance_xor(int x, int y) { int count = 0, n = x ^ y; while (n) { ++count; n &= n - 1; } return count; } int hamming_distance_library(int x, int y) { return bitset<32>(x^y).count(); } int main() { int num_1 = 8; int num_2 = 1; cout<<"Hamming distance using xor is = "<<hamming_distance_xor(num_1, num_2)<<endl; cout<<"Hamming distance using library function is = "<<hamming_distance_library(num_1, num_2)<<endl; }
Output:
Hamming distance using xor is = 2 Hamming distance using library function is = 2