461. Hamming Distance
easyThe Hamming distance between two integers is the number of bit positions where they differ. Compute it as popcount(x XOR y). A clean one-liner.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
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.
Constraints
0 <= x, y <= 2^31 - 1
Examples
Example 1
x = 1, y = 42Explanation: The above arrows point to positions where the corresponding bits are different.
Example 2
x = 3, y = 11Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Step 1: which bit positions differ between x and y? XOR isolates exactly those bits.
Hint 2
Step 2: count the set bits in x ^ y. That's the Hamming distance.
Hint 3
Use Brian Kernighan's n & (n - 1) trick to count set bits in time proportional to the number of differences.
Solution approach
Reveal approach
Compute diff = x ^ y; every set bit in diff marks a position where x and y differ. Count set bits in diff using Brian Kernighan: initialize count = 0, then while diff != 0 do diff = diff & (diff - 1) and count++. Return count. The first line is the conceptual leap; the second is the standard popcount. O(k) time where k is the number of differing bit positions (at most 32). O(1) space.
Complexity
- Time
- O(1) — at most 32 bits
- Space
- O(1)
Related patterns
- bit-manipulation
- xor
Related problems
- 477. Total Hamming Distance
- 191. Number of 1 Bits
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
Practice these live with InterviewChamp.AI
Drill Hamming Distance and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →