Calculate hamming distance between two integers

Given two integers, return the Hamming distance between the two. The Hamming distance is the total number of places where the corresponding bits are different in the binary representation of two integers.

For example,

 
We can easily solve this problem by taking the XOR of both integers. Since XOR cancels the same bits (1^1=0 and 0^0=0), it will result in an integer whose corresponding bits are different. Then the problem is reduced to counting the number of set bits in the resulting binary representation. There are several ways to achieve that:

1. Brute-Force Solution

A simple solution is to check each bit of the integer (say n) and keep track of the set bit count. We can use the expression n & 1 to get 1 or 0 depending on whether the last bit of n is set or unset and the right shift operator (n >>= 1) to discard the least significant bit (LSB). Note that this will require one iteration per bit. Therefore, it loops through 32 times for a 32–bit integer.

2. Using Brian Kernighan’s Algorithm

Alternatively, we can use Brian Kernighan’s bit counting algorithm to count set bits in an integer. The algorithm uses the expression n & (n-1) to flip the rightmost set bit of an integer n. Here, n-1 flips all the bits after the rightmost set bit of n, including the rightmost set bit.

3. Using Built-in functions

We may also use the built-in functions to return the number of set bits in the binary representation of the specified integer value. In GCC, you can use the __builtin_popcount() function to count the number of set bits. In Java, we have a similar method, Integer.bitCount(), for counting the set bits.