在 Integer 类中有这样一个函数 bitCount，他是计算二进制中 1 的个数，源码如下。如果暂时看不懂没关系，看到最后你就懂了。
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 的个数，除了上面的解决方式以外还有其他解决方式，解决方式非常多，我们来看下。
解法一
把数字 n 和 1 进行 与运算 ，运算完之后 n 往右移一步继续和 1 进行 与运算 ……，最多运算 32 次即可计算 int 类型中 1 的个数。
public int bitCount(int n) {
int count = 0;// 统计 1 的个数。
for (int i = 0; i < 32; i++) {
count += n & 1;
n >>>= 1;// 无符号右移
}
return count;
}
上面的分析中我们看到，如果数字 n 往右移了几步之后结果为 0 了，就没必要在计算了，所以代码我们还可以在优化一点。
public int bitCount(int n) {
int count = 0;
while (n != 0) {// 如果 n 等于 0 就没有 1 了，不需要在计算了。
count += n & 1;
n = n >>> 1;
}
return count;
}
解法二
也可以像上面那样计算，但数字不动， 1 每次往左移，如果 与运算 的结果不等于 0 ，表示当前位置是 1 ，需要累加。
public int bitCount(int n) {
int count = 0;
// 数字不动，1 往左移。
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0)
count++;
}
return count;
}
解法三
在位运算介绍中我们讲过 n&(n-1) 表示每次消去数字 n 的二进制中最右边的 1 ，举几个例子看下。
可以使用上面的方式，通过循环把二进制中的 1 全部消掉为止。
public int bitCount(int n) {
int count = 0;
// 每次消去数字n最右边的1，直到全部消掉为止。
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
还可以改成递归的写法，一行搞定。
public int bitCount(int n) {
return n == 0 ? 0 : 1 + bitCount(n & (n - 1));
}
解法四
在位运算介绍中我们讲过 n&(-n) 表示只保留数字 n 的二进制中右边第一个 1 ，其他的全部置为 0，我们用数字 n 不断减去它最右边的 1 ，直到 n 变为 0 为止。
public int bitCount(int n) {
int total = 0;
// 消去最右边的1。
while (n != 0) {
n -= n & (-n);
total++;
}
return total;
}
解法五
int 类型是 32 位，我们可以每 4 位一组把它分为 8 组，然后统计每组中 1 的个数，统计的时候直接查表即可。
public int bitCount(int n) {
int table[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int count = 0;
while (n != 0) {// 通过每 4 位计算一次，求出包含 1 的个数。
count += table[n & 0xf];
n >>>= 4;
}
return count;
}
0xf 的二进制是0b1111，它和 n 进行 与运算 每次截取 n 的低四位。
解法六
上面的几种实现方式要么使用循环要么使用递归，下面我们来看一些即不使用循环也不使用递归的解决方式。
在二进制中要么是 0 要么是 1 ，其中 1 就是我们要统计的数量，怎么把这些数字累加起来，其中一种方式就是把 32 位分成 16 组，每组计算 1 的个数，因为每组只有两个数字，最多也只能有 2 个 1 ，使用两位存储足够了。
00（二进制位）------->00（表示二进制位中1的个数，00是0，表示没有1）
01（二进制位）------->01（表示二进制位中1的个数，01是1，表示有1个1）
10（二进制位）------->01（表示二进制位中1的个数，01是1，表示有1个1）
11（二进制位）------->10（表示二进制位中1的个数，10是2，表示有2个1）
这样把每组 1 的个数用两位二进制表示，然后在计算他们的值。
这里的关键点是怎么计算每两位中 1 的个数，只要计算出来后面就简单了，这里有两种计算方式，一种是先运算再移位。
00000000000000000000000000001011
每两位一组
00 00 00 00 00 00 00 00 00 00 00 00 00 00 10 11 这是原式 1 。
每组中先保留左边的 1 (这里只保留左边的 1 ，右边的忽略)
00 00 00 00 00 00 00 00 00 00 00 00 00 00 10 10
然后往右移一位（这个时候每两位表示的数字值就是这两位中左边1的个数）
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 01 这个是结果 1 。
然后再统计原式 1 每组中右边 1 的个数(这里只统计右边的1，左边的忽略)
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 这个是结果 2 。
结果 1 和结果 2 相加。
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 10
这个时候每组数字就是真实的数值了，01 表示 1 ， 10 表示 2 ，总共有 3 个 1 。
这个就是先运算在移位，后面我们就可以使用上面的方式来统计了。
public int bitCount(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) + (n & 0x55555555);// 每两位之间统计1的个数。
n = ((n & 0xcccccccc) >>> 2) + (n & 0x33333333);// 每四位之间统计。
n = ((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f);// 每八位之间统计。
n = ((n & 0xff00ff00) >>> 8) + (n & 0x00ff00ff);// 每十六位之间统计。
n = ((n & 0xffff0000) >>> 16) + (n & 0x0000ffff);// 统计32位中1的个数。
return n;
}
上面 0x 开头的都是十六进制，直接看不太明白，我们把它转化为二进制看下。
上面一些十六进制的二进制位如下。
0xaaaaaaaa---->10101010 10101010 10101010 10101010 (1和0交替出现)
0x55555555---->01010101 01010101 01010101 01010101 (0和1交替出现)
0xcccccccc---->11001100 11001100 11001100 11001100 (两个1和两个0交替出现)
0x33333333---->00110011 00110011 00110011 00110011 (两个0和两个1交替出现)
0xf0f0f0f0---->11110000 11110000 11110000 11110000 (四个1和四个0交替出现)
0x0f0f0f0f---->00001111 00001111 00001111 00001111 (四个0和四个1交替出现)
因为 int 类型最多只有 32 个 1 ， 32 在二进制中就是 100000 ，总共 6 位，所以当超过 6 位计算的时候，比如每 8 位一组计算的时候，我们没必要把前面的变为 0 ，因为他已经超过 32 的范围了，最后我们只需要截取后面的 6 位即可，后面的 6 位截取可以使用 6 个 1 和他进行 与运算 ， 111111 也就是十进制 63 。
public int bitCount(int n) {
n = ((n & 0xaaaaaaaa) >>> 1) + (n & 0x55555555);
n = ((n & 0xcccccccc) >>> 2) + (n & 0x33333333);
n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;//63的二进制表示位00111111。
}
解法七
上面计算两位中 1 的个数的时候是先运算再移位，其实我们还可以先移位再运算，举个例子看下。
00000000000000000000000000111011
每两位一组。
00 00 00 00 00 00 00 00 00 00 00 00 00 11 10 11 这是原式 1 。
先往右移一位
00 00 00 00 00 00 00 00 00 00 00 00 00 01 11 01
然后每组中保留右边的 1 （因为先往右移了一步，所以这里右边的 1 实际上就是原式 1 中左边的 1 ）。
00 00 00 00 00 00 00 00 00 00 00 00 00 01 01 01 这个是结果 1 。
然后再统计原式 1 每组中右边 1 的个数(这里只统计右边的1，左边的忽略)
00 00 00 00 00 00 00 00 00 00 00 00 00 01 00 01 这个是结果 2 。
结果 1 和结果 2 相加。
00 00 00 00 00 00 00 00 00 00 00 00 00 10 01 10
这个时候每组数字就是真实的数值了，01 表示 1 ， 10 表示 2 ，总共有 5 个 1 。
后面的都非常类似了，看下代码。
public int bitCount(int n) {
// n先往右移一位，然后再统计1的个数。
n = ((n >>> 1) & 0x55555555) + (n & 0x55555555);
n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
n = (((n >>> 4) & 0x0f0f0f0f) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;
}
解法六和解法七的区别主要在于每组中高位的计算，假如计算每 8 位中前 4 位和后 4 位的值，我们画个图看下这两种方式的区别。
解法八
前面计算两位之间 1 的个数的时候，使用的是相加的方式，实际上还可以使用相减的方式，就是用这两位二进制数减去这两位中左边的数字，如下图所示。每两位之间计算之后，后面的基本上都一样了。
来看下代码，是不是很熟悉，这就是我们最上面提到的计算二进制中 1 的个数。
public int bitCount(int n) {
// 使用减法
n = n - ((n >>> 1) & 0x55555555);
n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
n = (((n >>> 4) & 0x0f0f0f0f) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 0x3f;
}
上面讲的最开始计算的时候都是先计算每两位二进制中 1 的个数，那么能不能先计算每三位，四位，五位……二进制中 1 的个数呢？当然是可以的，我们来看下。
解法九
假如刚开始的时候每四位一组计算二进制中 1 的个数，这里有两种解决方式，一种是使用加法，一种是使用减法，并且每种又有先运算在移位和先移位在运算两种方式，那么这样组合起来写法就比较多了。我们不全写，随便写两个就行了。使用加法比较简单，只需要把每一位相加即可。使用减法的时候先减去四位中的前三位，然后在减去四位中的前两位，最后在减去四位中的最高位，如下图所。
使用加法计算每四位二进制中 1 的个数。
public int bitCount(int n) {
n = (n & 0x11111111) + ((n >>> 1) & 0x11111111) +
((n >>> 2) & 0x11111111) + ((n >>> 3) & 0x11111111);
n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;
}
使用减法计算每四位二进制中 1 的个数。
public int bitCount(int n) {
n = n - ((n >>> 1) & 0x77777777) - ((n >>> 2) & 0x33333333) - ((n >>> 3) & 0x11111111);
n = (((n & 0xf0f0f0f0) >>> 4) + (n & 0x0f0f0f0f));
n = n + (n >>> 8);
n = n + (n >>> 16);
return n & 63;
}
上面代码中的二进制表示如下：
上面一些十六进制的二进制位如下。
0x77777777---->01110111 01110111 01110111 01110111
0x33333333---->00110011 00110011 00110011 00110011
0x11111111---->00010001 00010001 00010001 00010001
解法十
上面我们举例子中无论是两位还是四位他们都是能被 32 整除的，如果每 3 位一组或者每 5位一组能不能计算呢？实际上也是可以的，因为 3 和 5 都是不能被 32 整除的，所以计算的时候需要特殊处理下即可。我们先来看下刚开始的时候每 3 位一组计算 1 的个数的写法，也是分为多种写法，我们来看下。
使用加法计算每三位二进制中 1 的个数。
public int bitCount(int n) {
n = (n & 011111111111) + ((n >>> 1) & 011111111111)
+ ((n >>> 2) & 011111111111);
n = ((n + (n >>> 3)) & 030707070707);
n = ((n + (n >>> 6)) & 07700770077);
n = ((n + (n >>> 12)) & 037700007777);
return ((n + (n >>> 24))) & 63;
}
注意上面数字都是十进制，不是十六进制，大家把它改成十六进制也可以，他们的二进制表示如下：
011111111111---->01001001 00100100 10010010 01001001
030707070707---->11000111 00011100 01110001 11000111
07700770077----> 00111111 00000011 11110000 00111111
037700007777---->11111111 00000000 00001111 11111111
使用减法计算每三位二进制中 1 的个数。
public int bitCount(int n) {
n = n - ((n >>> 1) & 033333333333) - ((n >>> 2) & 011111111111);
n = ((n + (n >>> 3)) & 030707070707);
n = ((n + (n >>> 6)) & 07700770077);
n = ((n + (n >>> 12)) & 037700007777);
return ((n + (n >>> 24))) & 63;
}
解法十一
既然每三位可以计算，那么每 5 位，7 位……都是可以计算的，这样写下去的话答案就比较多了，可能永远都写不完了，其实无论怎么写，原理都是不变的，有兴趣的大家可以尝试写下，这里再写一个每 5 位二进制中计算 1 的个数，剩下的就不在写下去了。
使用加法计算每五位二进制中 1 的个数。
public int bitCount(int n) {
n = (n & 0x42108421) + ((n >>> 1) & 0x42108421) + ((n >>> 2) & 0x42108421)
+ ((n >>> 3) & 0x42108421) + ((n >>> 4) & 0x42108421);
n = ((n + (n >>> 5)) & 0xc1f07c1f);
n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
return n;
}
使用减法计算每五位二进制中 1 的个数。
public int bitCount(int n) {
n = n - ((n >>> 1) & 0xdef7bdef) - ((n >>> 2) & 0xce739ce7)
- ((n >>> 3) & 0xc6318c63) - ((n >>> 4) & 0x42108421);
n = ((n + (n >>> 5)) & 0xc1f07c1f);
n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
return n;
}
上面代码中的二进制表示如下：
0xdef7bdef---->11011110 11110111 10111101 11101111
0xce739ce7---->11001110 01110011 10011100 11100111
0xc6318c63---->11000110 00110001 10001100 01100011
0x42108421---->01000010 00010000 10000100 00100001
0xc1f07c1f---->11000001 11110000 01111100 00011111
