总结:正数的左移与右移,负数的无符号右移,就是相应的补码移位所得,在高位补0即可。
负数的右移,就是补码高位补1,然后按位取反加1即可。
算法
(位运算) $O(logn)$
迭代进行如下两步,直到 $n$ 变成0为止:
- 如果 $n$ 在二进制表示下末尾是1,则在答案中加1;
- 将 $n$ 右移一位,也就是将 $n$ 在二进制表示下的最后一位删掉;
这里有个难点是如何处理负数。
在C++中如果我们右移一个负整数,系统会自动在最高位补1,这样会导致 $n$ 永远不为0,就死循环了。
解决办法是把 $n$ 强制转化成无符号整型,这样 $n$ 的二进制表示不会发生改变,但在右移时系统会自动在最高位补0。
时间复杂度
每次会将 $n$ 除以2,最多会除 $logn$ 次,所以时间复杂度是 $O(logn)$。
from yxc老师~
int NumberOf1(int _n) {
unsigned int n = _n;
int s = 0;
while(n)
{
s += n & 1; // 看个位是不是1
n >>= 1; // 把个位取出来
}
return s;
}
};