n&(n-1)有很多用法

基本原理

n&(n-1)作用：将n的二进制表示中的最低位为1的改为0，先看一个简单的例子：

n = 10100(二进制），则(n-1) = 10011 ==》n&(n-1) = 10000

可以看到原本最低位为1的那位变为0。

求某一个数的二进制表示中1的个数

191. Number of 1 Bits

while(n > 0)  
{  
    count++;  
    n&=(n-1);  
}  

#include <iostream>  
#include <cstdio>  
using namespace std;  
int main()  
{  
    int n, count = 0;  
    cin>>n;  
    while(n > 0)  
    {  
        count++;  
        n&=(n-1);  
    }  
    cout<<count<<endl;  
    return 0;  
}  

判断一个数是否是2的次幂

[leetcode])(https://leetcode.com/problems/power-of-two/description/)

2的次幂肯定是2进制表示中某位上有个1，只有一个1，包括1也是2的0次幂

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

#include <cstdio>  
using namespace std;  
int main()  
{  
    int n, count = 0;  
    cin>>n;  
    if((n>0) && (!(n&(n-1))) == true)  
        cout<<"这个数是2的幂"<<endl;  
    else  
        cout<<"这个数不是2的幂"<<endl;  
    return 0;  
}

计算 n! 的质因数2的个数

容易得出N!质因数2的个数 = [N / 2] + [N / 4] + [N / 8] + ….

下面通过一个简单的例子来推导一下过程：N = 10101(二进制表示）

现在我们跟踪最高位的1，不考虑其他位假定为0，

则在

[N / 2]    01000
[N / 4]    00100
[N / 8]    00010
[N / 16]    00001

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

由此推及其他位可得：(10101)!的质因数2的个数为10000 - 1 + 00100 - 1 + 00001 - 1 = 10101 - 3(二进制表示中1的个数)

推及一般N!的质因数2的个数为N - （N二进制表示中1的个数）

这个证明其实挺简单的，仔细想想就能明白了。

针对 1..N 范围中的所有整数：

N/(k^1) 表示包含因子 k 的整数数量

N/(k^2) 表示包含因子 kk 的整数数量。这些所有能被kk整除的整数相乘会包含 2*N/(k^2) 个因子k，但因为这些数字也满足条件1，所以在条件1中已经计入一半，这里不需要再重复计入了。

N/(k^3) 表示包含因子 kkk 的整数数量。这些所有能被kkk整除的整数相乘会包含 3*N/(k^3) 个因子k，但是1/3在条件1中计入，1/3在条件2中计入，因此这里也只需要计入一次。

你看，上面三个加起来，就等于在 1..N 中所有能被 k、k^2、k^3 整除的整数之积包含的因子k的个数。继续推广开来，找到一个 m ，使得 N < k^m ，那么 Z = sum(N/(k^i)) (1<=i<m) 就是 1..N 中所有数字的积(也就是N!)中包含因子k的个数。

顺便说一下，这个题目有个变种，供扩展思考：N!的十进制表示中末尾有几个零？

链接