输入一个非负整数,求它变成二进制后1的个数
时间: 2023-05-31 09:19:43 浏览: 171
### 回答1:
可以使用位运算来求解。将该数不断右移一位,并判断最后一位是否为1,如果是则计数器加1。直到该数变为0为止。
具体实现如下:
```
def count_ones(n):
count = 0
while n > 0:
if n & 1 == 1:
count += 1
n >>= 1
return count
```
其中,`&`表示按位与运算,`>>`表示右移运算。
例如,对于输入的数字13,其二进制表示为1101,其中有3个1,因此输出为3。
```
>>> count_ones(13)
3
```
### 回答2:
将一个非负整数转换为二进制后,统计其中1的个数,是一道比较简单的算法题。
我们可以先将二进制数的最后一位与1进行与运算,如果结果为1,则说明最后一位为1,将计数器加1,之后右移一位,继续判断下一位是否为1,直到数字变为0为止。可以用以下代码实现:
```
int solution(int num) {
int count = 0;
while (num != 0) {
if (num & 1 == 1) {
count++;
}
num >>= 1;
}
return count;
}
```
上述代码中, num & 1 == 1 是一个与运算,判断num的最后一位是否为1,如果为1则计数器加1。之后num右移一位,相当于把最后一位删除,再次判断num的最后一位是否为1,直到num为0为止。
### 回答3:
计算一个非负整数在二进制中1的个数是一道经典的算法题,称为"汉明重量"(Hamming Weight)问题。
我们可以从二进制的角度来思考这个问题。一个二进制数的第n位是1还是0,可以通过把这个数与2的n-1次幂(1,2,4,8,16...)取"与"操作(&),如果结果为0,说明原数的第n位为0,否则为1。因此,我们可以用循环结构和位运算来实现这个算法:
1. 初始化一个计数器变量count为0;
2. 循环遍历该数的二进制位,例如对于一个32位整数,我们可以用一个从0到31的循环变量i来表示第i位;
3. 对于第i位,将原数与2的i次幂(1<<i)进行"与"操作,如果结果不为0,说明该位为1,count加1;
4. 循环结束后,count的值即为该数在二进制下的1的个数。
在实际编程中,我们通常可以使用__builtin_popcount()这个系统函数来实现,该函数能够高效地计算一个数的汉明重量。
总之,计算一个非负整数在二进制中1的个数是一道比较基础的算法题,需要熟练掌握位运算和循环结构的用法。