引入
今天介绍的两个算法都是位于Integer.java下的静态方法，一个是bitCount(),一个是reverse(),都是涉及到底层二进制操作的。感兴趣的朋友可以看看。
为此，我先来大致介绍下一些需要用到的基础知识，方便更多人可以看懂。
基础知识
1. 二进制与按位操作符
计算机进行整数的各种运算实际上都是二进制的各种运算，因为这些数都是以二进制存储在各种存储介质中的
比如：
3的二进制是11, 5的二进制是101等
按位与就是按二进制的位对齐进行与操作
比如：
011
& 101
= 001
即 3 & 5 = 1
只有这位的两个都为1结果才为1，其余情况都为0
其他按位操作符同理，比如或（|），异或（^）等
2. 移位操作符
介绍完了二进制和按位操作符
再来介绍下移位操作，就是把一个数左移或者右移多少位
比如10进制中左移一位，21 -> 210,左移相当于*10，右移相当于/10
同理二进制中就是*2 /2了
3<<1 -> 6
3>>1 -> 1
二进制表示：
11<<1 -> 110
11>>1 -> 1
问题
介绍完这些基础，可以进入正题了
有一个很简单的问题：计算一个int类型整数中二进制中1的个数
int类型就是说这个数由32位二进制组成
比如 1956 这个数，其实在计算机里被存储为：
0000 0000 0000 0000 0000 0111 1010 0100
//1024+512+256+128+32+4 = 1956
那我们怎么快速获取其中1的个数呢
数！对，可以直接出结果：6
但是计算机可没有图形识别呢（其实有的，不过我们讨论的是不是这方面）
能不能用上面的基本逻辑操作来得到答案呢？
答案是能的，有几种思路，由易到难来给各位解答一下，顺便推出本篇的主题bitCount()
解法1：
按位与，操作32步
每次&1,这样可以判断这个数最后一位是不是1（奇偶性也可这样判断）
然后再利用右移操作获取下一位，这样就可以了
大致代码如下：
public static int count0(int a) {
int count = 0;
while (a != 0) {
if ((a & 1) == 1) {
++count;
}
a >>>= 1;
}
return count;
}
上述代码中：
++count 的意思是count = count + 1；意思是count+1后再赋给count，相当于count自增了1（java里=是赋值的意思，右赋左，左边获得右边的值，==是等于的意思）
a >>>= 1 是a = a >>> 1 的简写,>>>是无符号右移的意思，意思是右移时补上的左边最后一位为0（java里最后一位0表正数，1表负数，如果用>>的话负数会补1从而导致1不断增加a永远不可能为0陷入死循环，所以用>>>）,每次将右移1位后的结果给自己
最后count就是1的个数
解法2：
a&(a-1),最多32步
我们注意到（反正不是我注意到的），a&(a-1)的结果刚好就是a去除掉最右一个1的结果
比如：
a = 3 : 11
a-1 = 2 : 10
a & (a-1) = 11 & 10 : 10
下面这个看起来更明显：
a = 1956：0000 0000 0000 0000 0000 0111 1010 0100
a-1 = 1955：0000 0000 0000 0000 0000 0111 1010 0011
a & (a-1)：0000 0000 0000 0000 0000 0111 1010 0000
是因为-1会将这个数第一个1的前的所有0（也只能是0）变成1（不够减），第一个1退位变成0，后面的保持不变
这样&的结果就是后面的0 1正常保留下来，最右一个1被消除掉，有点精妙哈~
由于这样的几个结果，所以反复对a进行上述操作即可
代码大致如下：
public static int count1(int a) {
int count = 0;
while (a != 0) {
a &= (a - 1);
++count;
}
return count;
}
就不解释啥了
解法3：
是java官方的解法，也就是本篇要重点介绍的，只需log32=5步，特别精妙~
大概思路是这样的，假设我们可以通过某种方法算出每2位的1的个数和：
比如：
1956：0000 0000 0000 0000 0000 0111 1010 0100
我们把它每两位隔开方便查看：
00 00 00 00 00 00 00 00 00 00 01 11 10 10 01 00
每两位来储存1的个数（我第2行统计了1的个数方便查看）：
00 00 00 00 00 00 00 00 00 00 01 10 01 01 01 00
0 0 0 0 0 0 0 0 0 0 1 2 1 1 1 0
注意是1的个数，从右到左第4对（第7 8位）从10变成了01是因为10这对1的个数为1
所以第5对由11变成了10，因为11=2=10，有两个1
同理可以每4位储存：
0000 0000 0000 0000 0000 0011 0010 0001
0 0 0 0 0 3 2 1
8位：
00000000 00000000 00000011 00000011
0 0 3 3
16位：
0000000000000000 0000000000000110
0 6
32位：
00000000000000000000000000000110
6
这样是不是就得到最后的结果了呢？110==6，好像是对的呢
还差一点（要消除第6位之后的影响，接下来会说），不过我们先来看看这种方式具体要怎么操作
我们可以倒着来看：
16位->32位的时候
可以通过移位操作获取结果
前16位 后16位，对位相加(只写出前16位)
0000000000000110
+ 0000000000000000
= 6
代码：
i + (i>>>16) & 111111
为什么要 & 6个1呢
因为结果最大也就是32（-1为32个1），所以6位保存就够了
前面的位出现1会影响结果（1956这个数太小导致后16位没有1），故而要去掉
那么8到16同理：
i +(i>>>8)
4到8：
(i + i>>>4) & 0f0f0f0f //00001111……
0f0f0f0f是16进制表示，每4位2进制合在一起表示成一个16进制的数（0-15中 0-9表示不变,a-f表示10-15），这个数即为00001111这样的序列（4组0f）
之所以要加一个与的数是因为结果有6位，有可能会影响到5 6位的结果
比如：
上述1956 4到8的时候,
如果只是(i + i>>>4)：
i = 0000 0000 0000 0000 0000 0011 0010 0001
i>>>4 = 0000 0000 0000 0000 0000 0000 0011 0010
那么右移后的0011中的11（第5 6位）会对最后的结果造成影响（结果是取前6位），所以需要用00001111这样的序列来去除影响
2到4：
(i & 33333333) + ((i>>>2) & 33333333) //0011……
又有了一些变化，好像&操作有了分配律？
其实不是的，分开的原因是2位无法储存4（10+10 == 100），为了让进位得到保存，所以先去掉应该去掉的部分再错位相加
比如：
i = 00 10 10 01
i>>>2 = 00 00 10 10
如果先计算上述之和那么第2对（第 3 4位）就会进位，进位的1会到第5位上，然后使用序列0011……消除影响就会把进位给消除了，而这个进位是最后的结果所需要的（的确是4个1啊咋办呢），所以这时候就需要分开与序列& 0011，然后再相加，这样进位的1就会被保留下来了，是不是很精妙~
那你可能会问，为什么4到8等后面的操作不需要分开呢？是这样的，后面即使进位也进不到要消除影响的位上去，所以可以先+再&
8到16 16到32 不需要&是因为结果只有6位，没必要做消除处理了，最后 & 111111（3f）即可（最后一步消除影响）
1到2：
最后的一步了，与2到4一样：
(i & 55555555) + ((i>>>1) & 55555555) //0101……
以上步骤倒着进行，即可得到结果了
然后我们来看一下官方算法：
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;
}
上述代码中0x表示16进制数的开头，不然没法区分是16进制还是10进制
其他的步骤好像都与我们的解法一样，但是仔细看好像第一步，即1到2的时候式子不同：
i = i - ((i >>> 1) & 0x55555555);
我们的式子为：
i = (i & 55555555) + ((i>>>1) & 55555555)
这两个式子是不是一样的呢？答案：
当然了！！！
要证明上述两个式子相同，即证明以下式子相同：
(i & 55555555) + ((i>>>1) & 55555555)<<1 == i
<< 1 前面说了，左移一位，*2的意思
不妨还是看前面这个数：1956
1956 = 0000 0000 0000 0000 0000 0111 1010 0101
1956/2 = 0000 0000 0000 0000 0000 0011 1101 0010
首先，1956与0101……这样的序列&，保留第1 3 5 …… 31这样的位（以下称奇数位）
然后，1956/2与0101……这样的序列&，保留自己的奇数位，保留1956的2 4 6 …… 32位（以下称偶数位）
然后，再左移1位，即将所有自己的奇数位左移1位，就变成1956的偶数位
最后，1956的偶数位与奇数位相加，即为1956本身
一个式子：
保留奇数位+ 保留的偶数位*2（回到原来的偶数位置）= 原数
所以不知道是不是这源码的作者玩了个小心机还是这样换了后性能提高？感觉是不想让我们看懂而装的一个 BIG B 吧哈哈哈
真是牛逼！！！
这算法别看着只是从32步提高到了5步，实际上可是N->logN的提升，只是N==32就提高了6倍之多，N==1024时只需要10步，这时候就已经提高了100+倍了，是很大很大……的提升了
另一个类似思想的算法
最后我们来看下Integer.java里的另一个类似算法，二者挨得很近，算法思想也基本一致：
public static int reverse(int i) {
// HD, Figure 7-1
i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
i = (i << 24) | ((i & 0xff00) << 8) |
((i >>> 8) & 0xff00) | (i >>> 24);
return i;
}
这算法是用来反转一个int数的二进制的，比如 3=00……11会被反转成11……00
大概思路说一下，还是用1956举例，就不写得很详细了：
0000 0000 0000 0000 0000 0111 1010 0100 = 1956
& 0101……
保留1 3 5……
左移1
变2 4 6……
或 原偶数位（现数为奇数位）
得到结果为：
奇数位和偶数位交换 1 2 交换 3 4交换，……31 32交换
下面同理
&0011……
12 34交换 56 78交换……
1234 5678交换
最后一步将12345678 位与最后8位交换
中间16位交换
即完成
为什么最后一步操作方式不一样呢
因为按照之前的操作来还需要两步：8位交换 16位交换
那为什么之前的不按这种操作来呢
因为移动8位之前，4位，太繁琐了，镜像交换是8个部分或（|）的结果
所以只有最后一步采取了这种方式（虽然在4到8时采取这种方式能一步到位但需要8个部分或在一起），而分开只需要6个部分进行或操作
不得不说还是考虑周到，而且想到了两种交换方式，这才是最牛逼的地方啊！
结语
这两个算法实际应用应该基本没有，但我们应该汲取的是其中归并处理数据的思想，将N变为logN，这一步，真的很精妙啊（虽然我是永远想不到的555……）
（本文首发于掘金 ，某乎同名@风景在云端）
