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 Sam K., 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
More Bit Manipulation practice problems
- 29. Divide Two Integers
- 78. Subsets
- 89. Gray Code
- 136. Single Number
- 137. Single Number II
- 187. Repeated DNA Sequences
- 190. Reverse Bits
- 191. Number of 1 Bits