算法：统计整数的二进制表达式中的bit位为1的位数（汉明重量），普通算法：应该是最先想到的算法了，从最低位开始，一位一位地统计是否为1，时间复杂度为o(n)，n为总bit数。优化算法:这个算法乍看很懵逼，但是仔细琢磨一下也能发现原理：n-1后，n的最低位的1被消除了，然后与n位与，n变为最低位1置为0后的新整数。
普通算法
public int bitCount(int num) {
int count = 0;
do {
if ((num & 1) == 1) {
count++;
}
num>>=1;
} while (num > 0);
return count;
}应该是最先想到的算法了，从最低位开始，一位一位地统计是否为1，时间复杂度为O(n)，n为总bit数。
优化算法
public int countBit2(int num) {
int count = 0;
while (num > 0) {
num = num & (num - 1);
count++;
}
return count;
}这个算法乍看很懵逼，但是仔细琢磨一下也能发现原理：n-1后，n的最低位的1被消除了，然后与n位与，n变为最低位1置为0后的新整数，如：
0b101100 减一 0b101011 最低位的1消除，0b101100 & 0b101011 = 0b101000
如此循环多少次就有多少个1，时间复杂度也是O(n)，但是这个n表示bit位为1的个数，总体是要比上一个优一点的。
当我们以为这已经是最优的算法了，事实却并非如此
Integer.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;
}最后,其实java的Integer类已经提供了一个方法来统计bit位（无符号右移，可以统计负数的），乍看之下，WTF?
原理：想象一下，当一列的1摆在我们人脑的面前，我们会怎么数？一个一个数，第一个的算法的原理。或者两个两个地数？本方法就是如此实现的。如下图：
立即学习“Java免费学习笔记（深入）”；
二进制 十进制
1 0 1 1 1 1 1 1 1 1 10 11 11 11 11
01 10 10 10 10 1 2 2 2 2
\ / \ / \/ \/
01 0100 0100 1 4 4
\ / \ /
01 1000 1 8
\ / \ /
1001 9
767的二进制中的1的位数计算过程每两位bit为一组，分别统计有几个1，然后把结果存到这两个bit位上，如：11有2个1，结果为10，10替代11的存储到原位置。然后进行加法计算，把所有的结果加起来。加的过程中呢又可以两两相加，减少计算流程。
两个bit计算1的数量：0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1，这样就清楚了。
算法实现如下：
首先整数i抹除左一位：
i & 0x55555555，然后错位相加。(i >>> 1) & 0x55555555表示：左位移到右边，再把左位抹除，这样就可以计算两个bit位上1的个数了：0b1011=>0b0001 + 0b0101 = 0b0110左两位有1个1，右两位有2个1。这时
i中存储了每两位的统计结果，可以进行两两相加，最后求和。
过程：
0x55555555 0b01010101010101010101010101010101 0x33333333 0b00110011001100110011001100110011 0x0f0f0f0f 0b00001111000011110000111100001111 0x00ff00ff 0b00000000111111110000000011111111 0x0000ffff 0b00000000000000001111111111111111 0x3f 0b00111111 0b11 11 11 11 11 (i & 0x55555555) + ((i >>> 1) & 0x55555555) = 0b0101010101 + 0b0101010101 = 0b1010101010 0b10 10 10 10 10 (i & 0x33333333) + ((i >>> 2) & 0x33333333) = 0b1000100010 + 0b00100010 = 0b1001000100 0b10 01 00 01 00 (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f) = 0b1000000100 + 0b0100 = 0b1000001000 0b10 00 00 10 00 (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff) = 0b1000 + 0b10 = 0b1010 0b00 00 00 10 10 (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff) = 0b1010 + 0 = 0b1010 dec 10
算法原型：
public static int bitCount(int i) {
i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
return i;
}时间复杂度O(1),可以，很ok了！但是写文章都要润色下的，别说算法了，然后优化过后的就是Integer中的实现了。
优化：
第一步：两个bit计算1的数量：
0b11: 0b01 + 0b01 = 0b10 = 2,0b10: 0b00 + 0b01 = 0b01 = 1。研究发现：2=0b11-0b1，1=0b10-0b1,可以减少一次位于计算：i = i - ((i >>> 1) & 0x55555555)第二步：暂时没有好的优化方法
第三步：实际是计算每个byte中的1的数量，最多8（0b1000）个，占4bit，可以最后进行位与运算消位，减少一次
&运算：i = (i + (i >>> 4)) & 0x0f0f0f0f第四,五步：同上理由，可以最后消位。但是由于int最多32（0b100000）个1，所以这两步可以不消位，最后一步把不需要的bit位抹除就可以了：
i & 0x3f
感悟：大道至简，看似复杂的算法，其实现原理却是我们大脑的简单思维逻辑
7 0b111 i = 7 - ((7>>>1) & 0x55555555) = 6 = 0b110 i = (6 & 0x33333333) + ((6 >>> 2) & 0x33333333) = 2 + 1 = 3 = 0b11 i = (3 + (i >>> 4)) & 0x0f0f0f0f = 3 & 0x0f0f0f0f = 3 = 0b11 i = 3 + (3 >>> 8) = 3 = 0b11 i = 3 + (3 >>> 16) = 3 = 0b11 i = 3 & 0x3f = 3
相关文章：
相关视频：
