输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路
- 需要一个循环结构，不断对输入数进行
无符号右移动。 - 在循环体的结构当中，使用适当的过滤器（1 这个整数）对输入数进行
逻辑与（&）操作：结构为 1 的时候计数（count）增加 1；否则选择跳过继续执行循环 结构。 - 当
无符号右移操作执行到终点时候（输入数变成 0），终止循环，同时返回最终计数的变量。
位运算基础知识
计算机对有符号数（包括浮点数）的表示有三种方法：原码、反码和补码（补码 =反码 + 1）。在 二进制里，是用 0 和 1 来表示正负的，最高位为符号位，最高位为 1 代表负数，最高位为 0 代表正数。以 8 位的 byte 为例，最大值为：0111,1111，最小值为 1000,0000。
以此类推，在 Integer 的情况下，-5（toBinaryString）的结果为：1111,1111, 1111,1111,1111,1111,1111,1011。
右移
打印 -3 >> 1：-2。这里看一下具体的计算过程（正数左补 0，负数左补 1）：
- Integer.toHexString(-3) 得到 3 的 16 进制：0xfffffffd（此为-3的补码,计算机中负数用补码表示）。
- 将其转换成2进制为1111,1111,1111,1111,1111,1111,1111,1101。
- 右移一位得到：1111,1111,1111,1111,1111,1111,1111,1110，显而易见此为-2补码。
左移
打印 -3<<1：-6。左移相对来说比较简单（正负数皆右补 0）：
- -3 的二进制为：1111,1111,1111,1111,1111,1111,1111,1101。
- 左移一位为：1111,1111,1111,1111,1111,1111,1111,1010，其为-6的补码。
无符号右移
打印 -3<<1：2147483646。遵循的原则：正数左补 0，负数左补 1：
- -3 的二进制为：1111,1111,1111,1111,1111,1111,1111,1101。
- 无符号右移，高位补 0 得到：0111,1111,1111,1111,1111,1111,1111,1110，其为 2147483646 的补码/原码（正数的原码和补码相同）。
消失的无符号左移
为什么没有无符号左移？
因为左移是在后面补 0，而右移是在前面边补 1 或 0，有无符号是取决于数的第一位是 0 还是 1，所以右移是会产生到底补1还是0的问题。而左移始终是在右边补，不会产生符号问题，所以没有必要无符号左移 <<<。因此，无符号左移 <<< 和左移 << 是一样的概念。
常规代码实现
根据上述的思路和基本概念，这里用 JS 来对这道题进行解答：
function NumberOf1(n) {
// write code here
let count = 0
for(;n != 0; n >>>= 1) {
if(n & 1) {
count++
}
}
return count
}
Python 中遇到的问题和解决方法
Python 中没有无符号右移
在 JS 中，可以使用 a >>> b 来实现无符号位移，Python 中没有这个运算符，只能自己实现了
无符号右移 >>>：就是将有符号 int a 和 b 转为无符号 uint 后，再进行普通右移 >> 运算。比如 -1 的有符号 int 就是 -1，无符号 int 就是 4294967295。
因为 Python 中没有 无符号右移，因而不能对最高位补 0，对于 负数 还是继续用 1 补进，这样就没有办法正确的统计 1 的个数。
解决方法
解决前：
- Python：打印 -3 >> 1，输出 -2（不符合要求）
- JavaScript：打印 -3 >>> 1，输出 2147483646（符合要求）
解决后：
- Python：打印 (-3 & 0xffffffff) >> 1，输出 2147483646（符合要求）
原理：负数与边界数按位与（&） 操作后 得到的是对应二进制数的真值：
-3 & 0xffffffff —> 4294967293
此时再在 Python 当中对其进行正常右移 >> 操作则是对一正数进行右移，前面补 0，符合要求；如果没进行这一步操作，右移依然是针对负数来进行操作的，前面补 1，不符合要求。
代码实现
有了以上的原理铺垫，在 Python 的代码当中，在第一次右移操作之前，先对被操作数进行和边界数 0xffffffff 的 与 & 运算，可得到正确的执行结果：
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
n = n & 0xffffffff
while n != 0:
if (n & 1) == 1:
count += 1
n = n >> 1
return count
其他的解决办法
class Solution:
def NumberOf1(self, n):
# write code here
M1 = 0x55555555
M2 = 0x33333333
M4 = 0x0f0f0f0f
M8 = 0x00ff00ff
M16 = 0x0000ffff
n = (n & M1) + ((n >> 1) & M1)
n = (n & M2) + ((n >> 2) & M2)
n = (n & M4) + ((n >> 4) & M4)
n = (n & M8) + ((n >> 8) & M8)
n = (n & M16) + ((n >> 16) & M16)
return n
网友评论