Hamming Distance

• LeetCode: Hamming Distance
• Problem:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

• Note:

0 ≤ x, y < 2^31.

• Exmaple:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

• Analysis:

Using XOR(Exclusive or) operands to get different bits of two numbers, and count the number of bit is 1.

Truth Table:

   --------------
   | X | Y | XOR|
   --------------
   | 0 | 0 |  0 |
   --------------
   | 0 | 1 |  1 |
   --------------
   | 1 | 0 |  1 |
   --------------
   | 1 | 1 |  0 |
   --------------

• Code - Java:

class Solution {
    public int hammingDistance(int x, int y) {
        int val = x ^ y;
        int result = 0;
        while (val > 0) {
            result += (1 & val);
            val >> 1;
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    int hammingDistance(int x, int y) {
        int val = x ^ y;
        int count = 0;
        while (val > 0) {
            count += 1 & val;
            val >>= 1;
        }
        return count;
    }
};

• Code - Python:

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        val = x ^ y
        count = 0
        while val > 0:
            count += 1 & val
            val >>= 1
        return count

• Code - C:

int hammingDistance(int x, int y) {
    int val = x ^ y;
    int count = 0;
    while (val > 0) {
        count += 1 & val;
        val >>= 1;
    }
    return count;
}