请实现一个函数，输入一个整数，输出该数二进制表示中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;
}
网友评论