461.md

Question:

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.

Analysis

这题非常容易，解法一是个非常直观的解法，既然题目的意思是，找两个数按比特位来看，不同的比特位，那好了，依次取最后一位，计算是否相同，然后算完之后，两数右移一位，再接着重复算。

当然了，还有一种，道理相同，就是稍微有点改进的是，一开始先将x和y异或，最再用上面的方法来算，这样可以避免比较两次，这是解法二。

解法三就有点意思了，这里利用了一个位运算的奇技淫巧，那就是x&(x-1)可以移除x转成二进制后面的0，比如二进制的11000，与上10111之后就是10000了。

Tips

x&(x-1)可以移除x转成二进制后面的0

Code

// 解法一
func hammingDistance(x int, y int) int {
        var ret int
        for x != 0 || y != 0 {
                if x&1 != y&1 {
                        ret++
                }
                x >>= 1
                y >>= 1
        }
        return ret
}

//解法二
func hammingDistance(x int, y int) int {
        var ret int
        xor := x ^ y
        for xor != 0 {
                if xor&1 != 0 {
                        ret++
                }
                xor >>= 1
        }
        return ret
}

// 解法三
func hammingDistance(x int, y int) int {
        var ret int
        xor := x ^ y
        for xor != 0 {
                ret++
                xor &= xor - 1
        }
        return ret
}