Hamming Distance
XOR the two numbers, then popcount the differing bits.
2 min read
bit-manipulation
Problem#
Return the number of positions at which the corresponding bits of two integers differ.
Examples#
x=1, y=4→2(001vs100).x=3, y=1→1.
Constraints#
0 <= x, y <= 2^31 - 1.
Approach#
x ^ y has 1s exactly where the bits differ. Count those bits.
Solution#
class Solution {public: int hammingDistance(int x, int y) { return __builtin_popcount(x ^ y); }};import "math/bits"
func hammingDistance(x int, y int) int { return bits.OnesCount(uint(x ^ y))}class Solution: def hammingDistance(self, x: int, y: int) -> int: return (x ^ y).bit_count()function hammingDistance(x, y) { let z = x ^ y; let count = 0; while (z !== 0) { count++; z &= z - 1; } return count;}class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); }}function hammingDistance(x: number, y: number): number { let z = x ^ y; let count = 0; while (z !== 0) { count++; z &= z - 1; } return count;}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)), orO(1)with hardware popcount. - Space:
O(1).
Concept revision#
Related#