Hamming Distance

LeetCode 461 | Difficulty: Easy

Easy

Problem Description

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 1:

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:

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

Constraints:

• 0 <= x, y <= 2^31 - 1

Note: This question is the same as 2220: Minimum Bit Flips to Convert Number.

Topics: Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 56 ms)

Metric	Value
Runtime	56 ms
Memory	N/A
Date	2018-08-18

Solution

public class Solution {
    public int HammingDistance(int x, int y) {
        int n =  x ^ y;
	int count = 0;
	while (n != 0)
	{
		n = n & n - 1;
		count++;
	}
        return count;
    }
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.