学步园

刚刚在网上闲逛，看到reddit上关于最受欢迎的代码的讨论贴，上面有一小段非常有意思的代码：

unsigned int v; // to count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
    v &= v - 1;
}

能直接看出来这段代码想要干啥么？^_^

其实这段代码的作用是计算v的二进制位里1的个数……是不是有点囧？
那么它是怎么做到的呢？

为了方便说明，我们可以先给v一个默认的初值，比如321。这样v的二进制数字就是101000001。

现在开始第一轮循环：
v - 1 的二进制位此时很容易看出来：101000000。
那么 v &= v - 1 就相当于 v = 101000001 & 101000000，于是得到：v = 101000000。
可以发现，若在运算之前v最右边的数字是0，则 v - 1 将把它变成1；反之，最右边是1，则 v - 1 将把它变成0。因此我们可以知道，不论v最右边的数字是0还是1，经过本轮它都将变成0。

接着第二轮循环：
v - 1 >>> 101000000 - 1 >>> 100111111
v &= v - 1 >>> v = 101000000 & 100111111 >>> v = 100000000
这次的结果是非常有意思的。因为根据二进制位运算的规律，100……00 - 1 将得到 011……11，也就是说从低位开始连续的0，经过减1运算后会全部变成1，而第一个高位上的1将变成0。
又因为0与任何数（0或1）做位与运算，结果都将是0，因此 v &= v - 1 运算的实质是跳过所有低位连续的0，并把高位上第一个1改成0。

然后再看第三轮：
v - 1 >>> 100000000 - 1 >>> 011111111
v &= v - 1 >>> v = 100000000 & 011111111 >>> v = 0
此时v变为0，因此下一轮循环开始时循环跳出。
完整过程共计3轮，因此c等于3，恰好等于v中1的个数。

其实经过上面的分析，不难看出来c其实就是个计数器，每当 v &= v - 1 把v中的一个1改写成0时，c就会加1。

像上面这种技巧性很强的代码，平时是不多见的。不过在比较追求性能的时候可以考虑使用。因为这个算法每一轮循环都会定位到v中的一个1，比普通的移位计算法要快得多了。