Hamming Distance Explained

Problem Statement

Given two integers x and y, compute the Hamming distance, which is the number of positions where their binary representations differ. For example, for x = 1 (binary: 01) and y = 4 (binary: 100), the Hamming distance is 2. This problem tests your ability to use XOR to identify differing bits and count them efficiently.

Example

Input: x = 1, y = 4

Output: 2

Explanation: 1 = 001, 4 = 100. The bits differ at the second and third positions.

Code

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.hammingDistance(1, 4)); // 2
    }
}
            

def hamming_distance(x, y):
    xor = x ^ y
    count = 0
    while xor:
        count += xor & 1
        xor >>= 1
    return count

# Example usage
print(hamming_distance(1, 4))  # 2
            

function hammingDistance(x, y) {
    let xor = x ^ y;
    let count = 0;
    while (xor) {
        count += xor & 1;
        xor >>>= 1;
    }
    return count;
}

// Example usage
console.log(hammingDistance(1, 4)); // 2
            

Explanation

• Compute x ^ y to get a number where 1 bits indicate positions where x and y differ.
• Initialize a counter count to track these 1 bits.
• While xor is non-zero, extract the least significant bit using xor & 1.
• Add it to count and right-shift xor to process the next bit.
• Return the total count.

Note