Code Implementation

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # XOR will give a bit with 1 wherever x and y differ
        xor = x ^ y
        # Count the number of 1s in the binary representation
        return bin(xor).count('1')
      

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

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

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

Problem Description

The Hamming Distance problem asks: given two integers, x and y, calculate the number of positions at which the corresponding bits are different in their binary representations. In other words, for each bit position, check if the bit in x is the same as the bit in y. If not, count that position. Return the total count.

• Both x and y are non-negative integers.
• The integers are provided as input, and the output is a single integer representing the Hamming distance.
• All bits are considered, including leading zeros up to the length of the longer number.

Thought Process

To solve this problem, first consider what it means for two bits to be different. If you compare the binary representations of x and y bit by bit, every position where they differ should be counted.

A brute-force approach could involve converting both numbers to binary strings, padding them to the same length, and comparing each character. However, this is unnecessary because bitwise operations are designed for such tasks.

The key insight is to use the XOR operation (^). XOR returns 1 when the bits are different and 0 when they are the same. Thus, x ^ y gives a number whose binary representation has 1s exactly where x and y differ.

The final step is to count the number of 1s in the result, which directly gives the Hamming distance.

Solution Approach

• Step 1: Compute the XOR of x and y. This operation highlights all the bit positions where the two numbers differ.
• Step 2: Count the number of set bits (1s) in the result. Each 1 represents a differing bit position.
• Why this works: XOR is a bitwise operation that outputs 1 when the two input bits are different. Thus, the number of 1s in x ^ y is exactly the number of differing positions.
• Counting set bits:
  • In Python, you can use bin(val).count('1') to count 1s.
  • In C++, Java, and JavaScript, you typically use a loop: check the least significant bit, increment a counter if it's 1, and right-shift until the number is zero.
• Why not brute force? Converting to strings and comparing is slower and more error-prone. Bitwise operations are faster and more direct for this problem.

Example Walkthrough

Consider x = 4 and y = 1.

• Binary of 4: 100
• Binary of 1: 001

Comparing bit by bit (from right to left):

• Rightmost bit: 0 (from 4) vs 1 (from 1) → different (count = 1)
• Middle bit: 0 vs 0 → same (count remains 1)
• Leftmost bit: 1 vs 0 → different (count = 2)

So, the Hamming distance is 2.

Using XOR: 4 ^ 1 = 5, which is 101 in binary. There are two 1s in 101, matching our count.

Time and Space Complexity

• Brute-force approach:
  • Convert numbers to binary strings, pad, and compare each character.
  • Time complexity: O(L), where L is the length of the binary representation (number of bits).
  • Space complexity: O(L) for the binary strings.
• Optimized approach (bitwise):
  • XOR is O(1) for fixed-width integers.
  • Counting set bits is O(K), where K is the number of bits in the integer (typically 32 or 64, so effectively constant time).
  • Space complexity: O(1), since only a few integer variables are used.

Summary

The Hamming Distance problem is efficiently solved using bitwise operations. By leveraging XOR to identify differing bits and counting set bits, we avoid unnecessary conversions and comparisons. This approach is both elegant and optimal, making full use of the properties of binary arithmetic and bit manipulation.

The key insight is that XOR pinpoints differences, and counting 1s gives the answer directly. This method is fast, concise, and works across all major programming languages.