Bit Manipulation — Hamming Distance
↗ LeetCode: Hamming Distance · Easy · pattern chapter →
Asked atMetaAmazonGoogleAdobe
Return the number of positions where the bits of x and y differ.
Example 1 — x=1, y=4 → 2Example 2 — x=3, y=1 → 1
Constraints — 0 ≤ x, y ≤ 2³¹−1. Brute char-by-char binary compare is O(32) = 32 ops. Integer.bitCount(a ^ b) is 1 XOR + 1 popcnt intrinsic = 2 CPU cycles — ~10⁹ ops/sec on modern hardware.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach — Popcount of XOR
Insight. x XOR y has 1s exactly at differing positions → answer is popcount(x^y).
java
int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}Complexity — Time O(1); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Popcount of XOR | O(1) | O(1) | optimum |
When to use which
- "Sum of pairwise Hamming distances" → per-bit counting; see Total Hamming Distance.
- Manhattan-like "min flips to reach y" → same popcount.
AI Study CompanionBeta
Related problems
- Total Hamming Distance
- Number of 1 Bits
- [XOR Sum problems]
Was this page helpful?
📚 Related problems