Hamming Distance Problem

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, return the Hamming distance between them.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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.

Example 2:

1
2
3
4

Input:
x = 3, y = 1
Output:
 1

Constraints:

  • 0 <= x, y <= 231 - 1

Solution

Method 1 – Bitwise XOR and Counting

Intuition

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. By taking the XOR of the two numbers, we get a number whose set bits represent differing positions. Counting these set bits gives the Hamming distance.

Approach

  1. Compute the XOR of x and y.
  2. Count the number of set bits in the result.
  3. Return the count as the Hamming distance.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int ans = 0;
        while (xor != 0) {
            ans += xor & 1;
            xor >>= 1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xorv = x ^ y, ans = 0;
        while (xorv) {
            ans += xorv & 1;
            xorv >>= 1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func hammingDistance(x int, y int) int {
    xor := x ^ y
    ans := 0
    for xor != 0 {
        ans += xor & 1
        xor >>= 1
    }
    return ans
}
1
2
3
4
5
6
7
8

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        ans = 0
        while xor:
            ans += xor & 1
            xor >>= 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn hamming_distance(x: i32, y: i32) -> i32 {
        let mut xor = x ^ y;
        let mut ans = 0;
        while xor != 0 {
            ans += xor & 1;
            xor >>= 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    hammingDistance(x: number, y: number): number {
        let xor = x ^ y, ans = 0;
        while (xor !== 0) {
            ans += xor & 1;
            xor >>= 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(1), since the number of bits is fixed (32).
  • 🧺 Space complexity: O(1), only a few variables are used.

Method 2 – Bitwise XOR and Brian Kernighan’s Algorithm

Intuition

Brian Kernighan’s algorithm efficiently counts the number of set bits by repeatedly clearing the lowest set bit. This reduces the number of iterations to the number of set bits.

Approach

  1. Compute the XOR of x and y.
  2. While the result is not zero, increment the count and clear the lowest set bit.
  3. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x ^ y, ans = 0;
        while (xor != 0) {
            ans++;
            xor &= xor - 1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int hammingDistance(int x, int y) {
        int xorv = x ^ y, ans = 0;
        while (xorv) {
            ans++;
            xorv &= xorv - 1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func hammingDistance(x int, y int) int {
    xor := x ^ y
    ans := 0
    for xor != 0 {
        ans++
        xor &= xor - 1
    }
    return ans
}
1
2
3
4
5
6
7
8

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        ans = 0
        while xor:
            ans += 1
            xor &= xor - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn hamming_distance(x: i32, y: i32) -> i32 {
        let mut xor = x ^ y;
        let mut ans = 0;
        while xor != 0 {
            ans += 1;
            xor &= xor - 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    hammingDistance(x: number, y: number): number {
        let xor = x ^ y, ans = 0;
        while (xor !== 0) {
            ans++;
            xor &= xor - 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(1), since the number of bits is fixed (32).
  • 🧺 Space complexity: O(1), only a few variables are used.