面试题15：二进制中1的个数

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。

解析：有两个解法：第一种是类似于独热的扫描，从右到左扫描，当扫描到当前位为 1 就给计数器加一。第二种是从右到左依次把 1 变成 0，这里用到的一个技巧是 可以把 的二进制表示中的最右边的 1 变成 0。变一次就给计数器加一。

答案：

int NumberOf1_Solution1(int n)
{
    int cnt = 0, flag = 1;

    while (flag) //flag 左移 31 次之后，再左移就变成 0 了
    {
        if (n&flag) ++cnt;
        flag <<= 1;
    }
    return cnt;
}

int NumberOf1_Solution2(int n)
{
    int count = 0;

    while (n)//n 中最左边的那个 1 被消除之后，n 就变成了 0
    {
        ++count;
        n &= n-1; //将 n 的最右边的 1 变成 0
    }

    return count;
}