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
}