How do you approach Hamming Distance?

Which single bitwise operation produces a 1 exactly in the positions where two numbers differ?

What is the time complexity of Hamming Distance?

Time complexity: O(k) where k is the number of differing bits (at most ~30 here). Space complexity: O(1).

What are common mistakes on Hamming Distance?

Shifting by at least the word width, which is undefined or wraps depending on the language. Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends. Precedence: & and | bind more loosely than the comparison operators, so a & 1 == 0 does not mean what it looks like.

gitGood.dev

← Back to problems

Hamming Distance

EasyAlgorithms

Description

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

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

Example 1

Input: x = 1, y = 4

Output: 2

Explanation: 1 is 0b001 and 4 is 0b100 - they differ in two bit positions.

Example 2

Input: x = 3, y = 1

Output: 1

Example 3

Input: x = 0, y = 0

Output: 0

Constraints

- 0 <= x, y <= 10^9

Hamming Distance: approach, complexity and pitfalls

An easy bit manipulation problem, graded against 7 test cases (4 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

Which single bitwise operation produces a 1 exactly in the positions where two numbers differ?
After computing x XOR y, the problem reduces to counting the 1 bits of one number.
Count set bits with a loop: while z > 0, add (z & 1) and shift z right. Or use z & (z - 1) to clear the lowest set bit each iteration.

The optimal approach

Show the approach: XOR + Popcount

`x ^ y` produces a number whose 1 bits sit exactly where `x` and `y` disagree. Counting those 1 bits gives the Hamming distance. The Brian Kernighan trick `z &= z - 1` clears the lowest set bit, so the loop runs once per differing bit.

Time: O(k) where k is the number of differing bits (at most ~30 here)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.