Hamming Distance

XOR the two numbers, then popcount the differing bits.

Easy
Time O(log max) Space O(1)
LeetCode
2 min read
bit-manipulation

Problem#

Return the number of positions at which the corresponding bits of two integers differ.

Examples#

  • x=1, y=42 (001 vs 100).
  • x=3, y=11.

Constraints#

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

Approach#

x ^ y has 1s exactly where the bits differ. Count those bits.

Solution#

Hamming Distance
class Solution {
public:
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
};

Editorial#

XOR is the bit-difference operator. __builtin_popcount compiles to a single instruction on most architectures. A portable equivalent is Brian Kernighan’s loop: while (z) { ++c; z &= z - 1; }.

Complexity#

  • Time: O(log max(x, y)), or O(1) with hardware popcount.
  • Space: O(1).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.