有哪些令人拍案叫绝的代码/优化?
印象比较深的一个：计算二进制中的1的个数
很多年前从Matrix67 看到的，传送门：
Matrix67: The Aha Moments比如 0x13， 表示成二进制是 00010011 一共有 3 个 1。这个操作在计算海明距离的时候十分有用，将两个操作数异或然后统计有多少个 1 就是海明距离。
很容易想到直接按位统计的算法：
int bits(uint32_t x) {
int ans = 0;
while (x) {
ans += x & 1;
x >>= 1;
}
return ans;
}
这个方案的时间和输入整形的最高位1有关，如果这个数正好是 2^31的话，那么耗费32个单位的时间。
能不能给力一点呢？
这里就要先介绍一个位运算操作，Lowbit，即计算一个整形中最低的那位1是什么。
int lowbit(int x) {
return x & -x;
}我们都知道，计算机中整数是用补码表示的，一个数的取负就是这个数按位取反再加一，举个例子
原值 00100100
取反 11011011
取负 11011100
原值 00100100
（原值写了两遍）可以发现一个数和它取负只有原值的最低位1都为1。这样 x & -x 就可以把原来的最低位取出来了。
这样，计算1的个数的代码可以改为
int bits(int x) {
int ans = 0;
while (x) {
ans ++;
x -= x & -x;
}
return ans;
}
这个方案的复杂度和输入中1的个数有关，有几个1消耗几个单位的时间，还算不错。
能不能再给力一点呢？
可以
int bits(int x){
x=(x & 0x55555555) + ((x >>1 ) & 0x55555555);
x=(x & 0x33333333) + ((x >>2 ) & 0x33333333);
x=(x & 0x0f0f0f0f) + ((x >>4 ) & 0x0f0f0f0f);
x=(x & 0x00ff00ff) + ((x >>8 ) & 0x00ff00ff);
x=(x & 0x0000ffff) + ((x >>16) & 0x0000ffff);
return x;
}
这个代码一眼看上去就晕了是正常的，很多年前我看到也吓尿了。
其实这是优化是分治法和利用处理器字并行的结合。（也可以认为是一种SIMD（Single Instruction Multiple Data），就是一条指令处理多个数据）
先说这个方案如何分治的，我们用 0x35 举例，他的二进制是00110101
(这里应该有一张二叉树)
我们先把每2位二进制中的1算出来，然后每4位，然后每8位
（知乎代码块在手机和移动端浏览器缩进都不对，不要怪我）
1bit (00)(11)(01)(01)
2bit ( 0)( 2)( 1)( 1)
4bit ( 2)( 2)
8bit ( 4)用这种方法，我们最终可以得到原数中一共有4个bit为1
再来说并行。首先给一句废话：2个bit里面最多有两个 bit 为 1，四个里面最多有 4 个bit为1，由此我们可以知道，一段01串里的1的个数再表示称整形，长度不会超过原串的长度。（比如 1111 有 4 个 1，把4表示成二进制是0100，不超过四位）
OK，我们有办法把在一次加法计算中把每两位的1都求出来吗？ YES
// (00)(11)(01)(01) => ( 0)( 2)( 1)( 1)
0x55 = 01010101 的意义相当于一个筛子，只允许奇数位的数字通过
0x55: 01|01|01|01
x: 00|11|01|01
x & 0x55: 0| 1| 1| 1
x >> 1: 00|01|10|10
(x>>1) & 0x55: 0| 1| 0| 0
+: 00|10|01|01
0| 2| 1| 1
看到这应该大概懂了，就是把偶数位的1向右对齐一下，再和奇数位的1求个和，这个过程中每两位是并行的。
然后计算每4位的和
// ( 0)( 2)( 1)( 1) => ( 2)( 2)
x: 0010|0101
0x33: 0011|0011
x & 0x33: 10| 01
x >> 2: 0000|1001
(x >> 2) & 0x33: 00| 01
+: 0010|0010
: 2| 2
后面的依此类推。
就这样，首先吧 32 个 1 位整形加成 16 个2 位整形，再加成 8 个4 位整形，4 个 8 位整形，2 个16位整形，1 个 32位整形，这么推下来就能统计出一个整形里面有多少个1啦。
而且，一个if都没有。
--2016-11-19 更--
经
@擎天柱同学提醒，这玩意有CPU指令处理了，2008年的SSE4.2 已经引入了 popcnt 系列指令专门处理计数问题。这里还有一篇很好的文章，对各种算法做了分析
popcount 算法分析 - KAlO2 - 博客园G++ 的使用方法很简单，使用 __builtin_popcount 函数，编译时加入 -mpopcnt 标志
然而我刚才测试的时候发现了一个切合本题的新东西，按说有指令集支持的情况下用专用指令是最快的，但是在G++ 5.3 O3 优化下，本文提到的 parallel_popcnt 算法竟然比 popcnt 指令还快。大概耗时是4：5的样子(parallel_popcnt: popcnt 指令)
这就有意思了，经过分析生成的汇编，发现如果你是批量计算pop_cnt 的话，因为 parallel_popcnt 算法是一个纯函数，所以可以被 G++ 使用 SSE 直接 SIMD 优化，一次计算4个int32 的 popcnt。
具体实现大概是使用了 5 个SSE 128 bit 寄存器储存那五个magic number，然后执行各种打包的右移操/求和/求与。
源码和汇编都在
https://gist.github.com/comzyh/5ba5ebeb0841661d1b006d3291404464放下关键的汇编：
# xmm6,7,8,9,10 分别对应那5个数 0x55555555
.L7:
movdqa (%rax), %xmm0 #取4个int32
addq $16, %rax
cmpq %rax, %r15
movdqa %xmm0, %xmm3 #拷贝一份
pand %xmm6, %xmm0 #(x & 0x55555555)
psrad $1, %xmm3 #x >> 1
pand %xmm6, %xmm3 #(x >> 1 ) & 0x55555555)
paddd %xmm0, %xmm3 #(x & 0x55555555) + ((x >> 1 ) & 0x55555555)
movdqa %xmm3, %xmm2
pand %xmm7, %xmm3
psrad $2, %xmm2
pand %xmm7, %xmm2
paddd %xmm3, %xmm2
movdqa %xmm2, %xmm1
pand %xmm8, %xmm2
psrad $4, %xmm1
pand %xmm8, %xmm1
paddd %xmm2, %xmm1
movdqa %xmm1, %xmm0
pand %xmm9, %xmm1
psrad $8, %xmm0
pand %xmm9, %xmm0
paddd %xmm1, %xmm0
movdqa %xmm0, %xmm1
pand %xmm10, %xmm0
psrld $16, %xmm1
paddd %xmm1, %xmm0
paddd %xmm0, %xmm4 # 我写的程序是求和，编译器直接每轮SIMD求4个和，程序结束才把这四个数加起来
jne .L7
至于CPU指令的方法，汇编就很简单了,一看就懂
.L9:
popcntl (%r14), %eax
addq $4, %r14
addl %eax, %r13d
cmpq %r14, %r15
jne .L9
当然，如果不是在连续内存中批量处理，还是 popcnt 指令快一点