0%

二进制中1的个数

发表于 更新于

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

令f(n)f(n)为n中1的个数。若n≠0n \ne 0，则在n-1中，n中最右边的1被置为0，而该1的左侧的1保持不变，故

f(n)=f((n−1)&n)+1f(n) = f((n-1)\& n) + 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
     int  NumberOf1(int n) {
         int c = 0;
         while (n)
         {
             c++;
             n &= (n - 1);
         }
         return c;
     }
};