算法笔记(1)——位运算技巧（x & (x−1)）

这个技巧出自Brian Kernighan算法，x&(x-1)可以用来把x最低位的1变成0，由此可以用来循环调用计算x这个数的二进制位的1的个数，同样也可以判断x是否为2的幂。

下面进行粗略的理解这个公式：

先考虑x和(x-1)在二进制上有什么区别，通过观察我们容易知道，(x-1)只影响从最低位一直到最低位的1的那一位，比如数0b11100，减去1后变成了0b11011，高位完全不影响,而x&x =x恒成立，所以对于x&(x-1),只需要考虑那些低位就可以。我们看x的低位，就是0b100这种形式，比如0b1,0b10,0b100,0b1000等等，然后毫无疑问减去1的话就得到了诸如：0b0,0b01,0b011,0b0111等等，也就是说刚好是取反了，这时将这两个数进行与运算，得到的就是0，所以这样是把x的最低位的1给抹除了，而不影响高位。