描述
输入一个整数,输出该数32位二进制表示中1的个数。其中负数用补码表示。
方法一:检查二进制每一位数字
我们通过右移操作消除第 i 位右边的数字,通过与 1 操作消除第 i 位左边的所有数字,对数字 n 重复32次这种操作就可以求得每一位的数字。
当我们要提取从右往左第3位数字时:
01101
>> 2 得到 00011
& 1 得到 00001
c++代码如下:
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
for (int i = 0; i < 32; i++)
res += (n >> i) & 1;
return res;
}
};
python3解法思路相同,
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
res = 0
for i in range(32):
res += (n >> i) & 1
return res
方法一切记不要只通过 >> 运算符进行操作,因为负数的右移操作会在数字最左端补 1 ,导致 n 始终不为0,造成无限循环。
方法二:通过位运算公式 n & (n - 1)
公式 n & (n - 1) 的作用是使 n 的二进制形式的最右边一个数字 1 变成 0
例如:
n = 001100
n - 1 = 001011
n & (n - 1) = 001000
每消除一个 1 计数一次,直到 n 变成 0,最后得到的计数就是 1 的个数。
class Solution {
public:
int NumberOf1(int n) {
int res = 0;
for (; n; n &= n - 1, res++);
return res;
}
};
python3与c++不同之处在于,c++中因为 n 是 32 位整数,所以当 n 为 -2147483648 时再减 1 会导致负数溢出(int 的范围是 [-2 ^ 31, 2 ^ 31 - 1]),溢出之后得到正数与运算结果为 0 不会导致死循环。但是 python 中的数字没有大小限制,在循环中减 1 后 n 依然为复数,n 始终不为 0 导致死循环。所以在 python 中需要先把 n 取成大正数。
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
res = 0
if n < 0: n &= 0xffffffff
while n:
res += 1
n &= n - 1
return res