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)