n&(n-1)的技巧

一道很简单的题目，计算某个32位无符号数中每个比特位1出现的次数，一开始直接遍历每个位，当然不可能遍历32个位，这样效率太低，4个位一起遍历，然后根据该4bit的值来直接switch出1出现的比特数，这样算法的时间复杂度是O(1)，只需要循环32/4=8次，当然结果是无误的，这样也打败了 100% 的cpp提交 ：） 当然这个实现的代码实在太长，太难看，于是搜下有没有什么好的解决方法，于是就搜到了这个 n&(n-1)。

貌似《编程之美》上提过这个，看来有空可以补补，自身某些方面知识有所欠缺是从工作的时候就知道的，当然欠缺的部分，对于工作是没有多大影响的，但是会限制高度，有空余时间还是得好好的查漏补缺，只是为了自己。

不谈别的了，先来看看这个小技巧，简单分析下。

比如当前有个数n=57，它的二进制表示为 11 1001，我们再来看下-1的结果 11 1000 ，我们将它们进行位与 11 1000，我们看到了最终的结果相比n，最右边的某bit位的1被抹除了。

再来看看借位的例子：

n=1101 1000 n-1=1101 0111 n&(n-1)=1101 0000

可以看到相比n，结果还是把最后一个1的比特位给抹除了，那么我们只要对n不断的进行这种操作，直到n为0，那么1的个数也就被计算出来了。