461. Hamming Distance

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, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

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.

Problem Summary

The Hamming distance between two integers refers to the number of positions at which the corresponding binary bits of the two numbers are different. Given two integers x and y, calculate the Hamming distance between them.

Note: 0 ≤ x, y < 231.

Solution Approach

• Find the Hamming distance between 2 numbers. The Hamming distance is defined as the total number of different binary bits between two numbers. This problem uses the bit operation X &= (X - 1) to continuously clear the lowest set bit. First XOR these two numbers; after the XOR, clearing the lower 1 bits gives the final answer.

Code

package leetcode

func hammingDistance(x int, y int) int {
	distance := 0
	for xor := x ^ y; xor != 0; xor &= (xor - 1) {
		distance++
	}
	return distance
}