求一个十进制数的二进制形式的1的个数

对于一个十进制数，当它为二进制形式的时候，如何知道它有多少个1呢？下面 我从三种方法来进行说明：

1. 除2的方法：

例如1011010，当它除2之后，结果为101101

101101，再除2，结果为10110，也就是说，当一个数%2 == 1时，说明存在一个1，这时候记录一次，直到这个数变成0之后，记录结束。

#include <bits/stdc++.h>
using namespace std;
const int M = 10000;

int main()
{
    int n, num;
    num = 0;
    cin >> n;
    while(n)
    {
        if(n % 2)
        {
            num++;
        }
        n /= 2;
    }
    cout << num << endl;
    return 0;
}

2.使用右移的方法（>>）

每次让这个数与1相与(&)，然后右移一位，同样可以统计1的个数

#include <bits/stdc++.h>
using namespace std;
const int M = 10000;

int main()
{
    int n, num;
    num = 0;
    cin >> n;
    while(n)
    {
        num += n & 0x01;
        n >>= 1;
    }
    cout << num << endl;
    return 0;
}

3.使用时间复杂度较小的方法

前两个方法都需要遍历二进制的所有0和1，这个方法直接对二进制中的1进行统计

例如，n=101101，将它和（n-1）相与，即n & (n-1)，结果为，101100，再进行n & (n-1)，结果为101000，以此类推。。

#include <bits/stdc++.h>
using namespace std;
const int M = 10000;

int main()
{
    int n, num;
    num = 0;
    cin >> n;
    while(n)
    {
        n &= n-1;
        num++;
    }
    cout << num << endl;
    return 0;
}