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.
Top comments (0)