n&=(n-1)的應用

n&(n-1)作用：将n的二進制表示中的最低位為1的改為0，先看一個簡單的例子：

n = 10100(二進制），則(n-1) = 10011 ==》n&(n-1) = 10000

可以看到原本最低位為1的那位變為0。

弄明白了n&(n-1)的作用，那它有哪些應用？

1. 求某一個數的二進制表示中1的個數

while (n >0 ) {

count ++;

n &= (n-1);

}

1. 判斷一個數是否是2的方幂

   n > 0 && ((n & (n - 1)) == 0 )

2. 計算N!的質因數2的個數。

   容易得出N!質因數2的個數 = [N / 2] + [N / 4] + [N / 8] + ….

   下面通過一個簡單的例子來推導一下過程：N = 10101(二進制表示）

   現在我們跟蹤最高位的1，不考慮其他位假定為0，

   則在

   [N / 2] 01000

   [N / 4] 00100

   [N / 8] 00010

   [N / 8] 00001

   則所有相加等于01111 = 10000 - 1

   由此推及其他位可得：(10101)!的質因數2的個數為10000 - 1 + 00100 - 1 + 00001 - 1 = 10101 - 3(二進制表示中1的個數)

推及一般N!的質因數2的個數為N - （N二進制表示中1的個數）