看了一道leetcode上面的题 461 ，Hamming Distance
计算两个整数有多少不同的位。其实很简单，取两个整数异或的值，然后计算出里面二进制有多少个1就行了。代码如下：
public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } 为什么要用bitCount来统计含1的位了？为什么不直接使用循环统计每个bit位了？
跳转到bitCount的源码中，如下：
public static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f;} 原来是 先 两个两个一组，求二进制1的个数，并且用两位二进制存储在原处，然后四个四个一组，求二进制位1的个数，再把它存储以4位二进制到原处。以此类推直到计算完成。 | src | store | remark |
|---|---|---|
| 00 | 00 | 这两位没有，那就用0存储 |
| 01 | 01 | 这两位只有一个1，就用1存储 |
| 10 | 01 | 这两位也只有一个1,也用1存储 |
| 11 | 10 | 这两位有两个1，用10存储 |
那么就一对一对的数，已知 src列 求出 store列？
列式计算：- 设 λλ = i - x
- 00 = 00 - 00;
- 01 = 01 - 00;
- 01 = 10 - 01;
- 10 = 11 - 01;
那么 x 又如何通过i得到呢？
我们手无寸铁，对CPU来说也只有加法和移位的手段。假如发明者列出这种算式，敏感的他一下子
很容易看出来： x=i>>>1 就这么简单 那么得到： λλ = i - (i>>>1)那么i不止两位怎么处理？如果这个是最后的两位，那么移位之后后面一位二进制可以抹掉
而前面的移位会影响后面的最高位，那么把移出去的那一位消除： i>>>1 & 01； 即为：01010101 01010101 01010101 01010101 λλ = i - (i>>>1 & 0x55555555)问题解决。
那么 计算了两位的如何计算4位的二进制位呢？ 枚举第一步计算完成的所有的情况：| src | target | remark | ref |
|---|---|---|---|
| 0000 | 0000 | = 0000 & 0011 | |
| 0001 | 0001 | = 0001 & 0011 | 01 = 01 & 11 |
| 0010 | 0010 | = 0010 & 0011 | 10 = 10 & 11 |
| 0100 | 0001 | = 01 + 00 | |
| 0101 | 0010 | = 01 + 01 | |
| 0110 | 0011 | = 01 + 10 | |
| 1000 | 0010 | = 10 + 00 | |
| 1001 | 0011 | = 10 + 01 | |
| 1010 | 0100 | = 10 + 10 |
后面两组可以参照第一组的结果，那么可以推算
四位中低两位 bb = aabb & 0011，主要要计算与高两位的和： 已知可以用1100& aabb =aa00得到左边的值，但是多了两个00，那么要计算aa + bb： 可以 aabb>>>2 = 00aa(bb)只看这两位，移位多出去的被00消除，不影响后面的计算。 即: λλ =( i & 0x0011) + (i>>>2 & 0x0011) 也就是: λλ =( i & 0x33333333) + (i>>>2 & 0x33333333)同理求8位里面的两边4位之和：
λλ =( i + i>>>4) & 0x0F0F0F0F求16位的两边之和：
λλ = i + (i >>> 8); 由于二等分是8位，而8位一共有4份。 A B C D(C>>>8) + D D处8位的结果最大为 0001 0000不会进位到C。
(B>>>8) + C C处8位的结果最大为 0001 0000不会进位到B。 (A>>>8) + B B处8位的结果最大为 0001 0000不会进位到B。 A + 0 A处最大结果为 0000 1000得到
A A+B B+C C+D 最后是求32位全部的内容也就是求(A+B)+(C+D) A A+B B+C C+D + 0 0 A A+B也就是
λλ= i + (i >>> 16) A A+B A+B+C A+B+C+D A+B+C+D最大也就32个： 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000 0000 0000 0000 0011 1111 = 0x3F 之所以要return i&0x3F，就是把前面抹干净。