#leetcode#191 Number of 1 Bits n&n-1的用处

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

思路1

n每次和1进行与运算，然后对n进行位运算，计算n中1的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res=0;
        int i=1;
        int a;
        while(n)
        {
            a=n&i;
            if(a!=0) res=res+1;
            n=n>>1;
        }
        return res;
    }
};

进行n&n-1运算，n&n-1每次把n的最低位变为0

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res=0;
        while(n)
        {
            res=res+1;
            n=n&(n-1);
        }
        return res;
    }
};

1，n&n-1，进行与运算，每次将n中的最低位的1变为0，可进行求解n中有多少个1的运算。

2，判断一个数是否是2的平方

3，计算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的个数）