题目描述

实现一个函数，输入一个整数，输出该数二进制表示中1的个数。

例如，把9表示成二进制是1001，则输出为2

常规解法

首先把n和1做位运算，判断n的最低位是不是1，然后把1左移一位得到2，再把n和2做位运算，判断n的次低位是不是1…这样反复左移。

循环的次数等于整数二进制的位数，32位的整数需要循环32次。

class Solution {

int NumberOfOne(int n){

int cnt = 0;

unsigned int flag = 1;

while(flag){

if(n & flag){

++cnt;

}

flag = flag << 1;

}

return cnt;

}

};

1

2

3

4

5

6

7

8

9

10

11

12

13

惊喜解法

把一个整数减去1，在和原整数做与运算，会把该整数最右边的1变成0。

那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

以1100为例，它减去1的结果是1011，再把1100和1011做位与运算，得到的结果是1000，

然后1000减去1，得到0111，与1000做位与运算，得到的结果是0000，故得到1100有两个1。

class Solution {

int NumberOfOne1(int n){

int cnt = 0;

while(n){

++cnt;

n = (n - 1) & n;

}

return cnt;

}

};

1

2

3

4

5

6

7

8

9

10

---------------------