Yesterday is history. Tomorrow is mystery. But today is a gift.
昨日已逝，明天尚远，今天才是老天赐予的礼物。
问题描述
之前我们有两篇是讲了位1的个数，没看过的可以看下，364，位1的个数系列（一）,385，位1的个数系列（二）。其中上一篇我们没有使用for循环以及while循环，使用的是相加的方式，今天我们讲的是和上一题非常相似的解法，相减的方式。
每两位存储
比如我们用两位数字存储的时候，我们只需要用这两位数减去偶数位上的值（从右往左数），比如
-
二进制00：00-0=00（表示有0个1）
-
二进制01：01-0=01（表示有1个1）
-
二进制10：10-1=01（表示有1个1）
-
二进制11：11-1=10（表示有2个1）
我们发现除了第一步和《位1的个数系列（二）》不同以外，其他的我们都可以完全按照上一题的方式来写，我们还是以-3为例来画个图看一下
上面的分析如果能够看的懂的话，那么代码就容易多了，我们来看下
1public static int bitCount(int i) {
2 i = i - ((i >>> 1) & 0x55555555);
3 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
4 i = (i + (i >>> 4)) & 0x0f0f0f0f;
5 i = i + (i >>> 8);
6 i = i + (i >>> 16);
7 return i & 0x3f;
8}
具体细节就不再这里分析了，如果想了解更多可以看《位1的个数系列（二）》
每3位存储
我们两位能存储，那么3位呢，看过《位1的个数系列（二）》的都知道，这也是可以的，之前我们介绍过的是通过一个个相加，也很好理解，那么这里如果使用的是相减应该怎么计算呢，我们来画个图看一下吧
通过上面的图分析我们找到了规律，就是每3位存储的话，只需要执行a=a-(a>>>1)-(a>>>2)就可以把数字存储到这3位数中，原理很简单，我们来看下代码
1public static int bitCount(int n) {
2 n = n - ((n >>> 1) & 033333333333) - ((n >>> 2) & 011111111111);
3 n = ((n + (n >>> 3)) & 030707070707);
4 n = ((n + (n >>> 6)) & 07700770077);
5 n = ((n + (n >>> 12)) & 037700007777);
6 return ((n + (n >>> 24))) & 63;
7}
结果对不对，我们只有找几组数据经过测试之后才具有说服力，我们顺便找几组数据测试一下
1 int num = 100000000;
2 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
3 num = Integer.MAX_VALUE;
4 System.out.println(num + "的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
5 num = 0;
6 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
7 num = -1;
8 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
9 num = Integer.MAX_VALUE - 10000;
10 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
11 num = Integer.MIN_VALUE;
12 System.out.println(num + "的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
我们再来看一下打印结果
1 100000000 的二进制是----->00000101 11110101 11100001 00000000 ---->1的个数是：12
2 2147483647的二进制是----->01111111 11111111 11111111 11111111 ---->1的个数是：31
3 0 的二进制是----->00000000 00000000 00000000 00000000 ---->1的个数是：0
4 -1 的二进制是----->11111111 11111111 11111111 11111111 ---->1的个数是：32
5 2147473647 的二进制是----->01111111 11111111 11011000 11101111 ---->1的个数是：26
6 -2147483648的二进制是----->10000000 00000000 00000000 00000000 ---->1的个数是：1
结果丝毫不差。
每多位存储
看明白了上面每3位存储的分析过程，那么这题解法就比较多了，我们可以类推每4位存储的时候我们只需要执行a=a-(a>>>1)-(a>>>2)-(a>>>3)，就可以把每4位1的个数存储在这4位数中，同理每5位存储的时候我们只需要执行a=a-(a>>>1)-(a>>>2)-(a>>>3)-(a>>>4)，就可以把每5位1的个数存储在这5位数中。每6位的时候……，那么这样写下去就非常多了。我们就分别以每4位和每5位为例来写一下。首先写的是每4位为一组来存储
1public static int bitCount(int n) {
2 int tmp = n - ((n >>> 1) & 0x77777777) - ((n >>> 2) & 0x33333333) - ((n >>> 3) & 0x11111111);
3 tmp = ((tmp + (tmp >>> 4)) & 0x0f0f0f0f);
4 tmp = ((tmp + (tmp >>> 8)) & 0x00ff00ff);
5 return ((tmp + (tmp >>> 16)) & 0x0000ffff) % 63;
6}
再来看一个每5位为一组来存储
1public static int bitCount(int n) {
2 n = n - ((n >>> 1) & 0xdef7bdef) - ((n >>> 2) & 0xce739ce7) - ((n >>> 3) & 0xc6318c63) - ((n >>> 4) & 0x02108421);
3 n = ((n + (n >>> 5)) & 0xc1f07c1f);
4 n = ((n + (n >>> 10) + (n >>> 20) + (n >>> 30)) & 63);
5 return n;
6}
我们随便找几组数据测试一下
1 int num = 1000;
2 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
3 num = Integer.MAX_VALUE;
4 System.out.println(num + "的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
5 num = 0;
6 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
7 num = -1;
8 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
9 num = -8;
10 System.out.println(num + " 的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
11 num = Integer.MIN_VALUE;
12 System.out.println(num + "的二进制是----->" + Util.bitInt32(num) + "---->1的个数是：" + bitCount(num));
我们就用最后一个每5位为一组的来测试一下，来看下结果
1 1000 的二进制是----->00000000 00000000 00000011 11101000 ---->1的个数是：6
2 2147483647的二进制是----->01111111 11111111 11111111 11111111 ---->1的个数是：31
3 0 的二进制是----->00000000 00000000 00000000 00000000 ---->1的个数是：0
4 -1 的二进制是----->11111111 11111111 11111111 11111111 ---->1的个数是：32
5 -8 的二进制是----->11111111 11111111 11111111 11111000 ---->1的个数是：29
6 -2147483648的二进制是----->10000000 00000000 00000000 00000000 ---->1的个数是：1
结果完全正确
总结
我们通过这3个系列，算是把这道题完全讲透了，这题虽然看似简单，但其中蕴含的解题思路确是非常多的，如果这题的所有解法都看懂了，那么对二进制的掌握程度将会有一个很大的提升。
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"赞"吧