Problem Statement

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

Given two integers x and y, return the Hamming distance between them.

Example:

Input: x = 1, y = 4
Output: 2
Explanation:
1  (in binary: 0001)
4  (in binary: 0100)
Bits differ at positions 2 and 3, so distance = 2

---

Approach 1: XOR + Bit Count

1. Use the XOR operation (^) on x and y.
   The XOR of two bits is 1 if they differ, 0 if they are the same.
   Therefore, the result of x ^ y will have 1s wherever the bits differ.
2. Count the number of 1s in the result (that’s the Hamming distance).
3. There are two ways to count bits:
   • Use Integer.bitCount() in Java.
   • Or manually count bits using bit shifting.

---

Java Solution

public class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;        // Step 1: XOR the two numbers
        int count = 0;
        while (xor != 0) {
            count += xor & 1;   // Step 2: Add 1 if the last bit is 1
            xor >>= 1;          // Step 3: Right shift
        }
        return count;
    }
}

Alternative using built-in method:

public int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}

---

Complexity Analysis

• Time Complexity: O(1) (since integer size is fixed, usually 32 bits)
• Space Complexity: O(1)

---

Dry Run

Input: x = 1 (0001), y = 4 (0100)

Step-by-step:

x ^ y = 0001 ^ 0100 = 0101  (binary for 5)
count = 0

Iteration 1: xor = 0101 → last bit 1 → count = 1
Iteration 2: xor = 0010 → last bit 0 → count = 1
Iteration 3: xor = 0001 → last bit 1 → count = 2
Iteration 4: xor = 0000 → done

Final count = 2

Output: 2

---