461. Hamming Distance

LeetCode 461. Hamming Distance

Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 2^31.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Tags

Bit Manipulation

Solution

Count the number of 1s in the result of x ^ y.

Complexity

• Time complexity: $O(1)$
• Space complexity: $O(1)$

Code

func hammingDistance(x int, y int) int {
	var ans int
	for z := x ^ y; z != 0; z >>= 1 {
		if z&1 == 1 {
			ans++
		}
	}
	return ans
}