513，汉明距离

Just don't be disappointed if there's not a pot of gold at the end of the rainbow. 

千万别失望，就算彩虹尽头没有你期待的美好也没关系。

问题描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：

0 ≤ x, y < 2^31.

示例:

输入: x = 1, y = 4

输出: 2

解释:

1   (0 0 0 1)

4   (0 1 0 0)

         ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

问题分析

x和y都转化为二进制的时候，在相同的位置上如果值都一样，他们的汉明距离就是0。如果在相同的位置上值不一样，有多少个不一样的位置，那么汉明距离就是多少。所以看到这道题，我们应该最容易想到的就是先异或运算，然后再计算这个异或运算的结果在二进制表示中1的个数。代码如下

1public int hammingDistance(int x, int y) {
2    return Integer.bitCount(x ^ y);
3}

一行代码搞定，这题实际上没什么难度，我们只需要计算x和y的异或结果，然后再计算这个结果的二进制中1的个数即可。在之前我们分3个系列分别讲到了二进制中1的个数

364，位1的个数系列（一）

385，位1的个数系列（二）

402，位1的个数系列（三）

当然这题答案非常多，下面我们再来看两种写法

1public int hammingDistance(int x, int y) {
2    int xor = x ^ y;
3    int res = 0;
4    while (xor != 0) {
5        res += xor & 1;
6        xor = xor >>> 1;
7    }
8    return res;
9}

或者

1public int hammingDistance(int x, int y) {
2    int xor = x ^ y;
3    int res = 0;
4    while (xor != 0) {
5        res += 1;
6        xor &= xor - 1;
7    }
8    return res;
9}

●499，位运算解只出现一次的数字 III

●495，位运算等多种方式解找不同

●494，位运算解只出现一次的数字

●469，位运算求最小的2的n次方