计算输入的数字在二进制下包含1的个数

type

status

date

slug

summary

📝 主旨内容

1.问题

计算输入的数字在二进制下包含1的个数

2.答案

思路1：

只要知道该数字二进制下各个位数上的数字，并且把数字是1的计入总数即可。

我们不妨借用我们最熟悉的10进制来思考该问题： 1234 1234%10=4 1234/10=123 123%10=3 123/10=12 12%10=2 12/10=1 1%10=1 1/10=0 相应的，如果是2进制的数字，譬如11，则： 11 其二进制为 1011 11%2=1 11/2=5 5%2=1 5/2=2 2%2=0 2/2=1 1%2=1 1/2=0 就这样，通过不断地%与/获得该数字在二进制下各个位数上的数字，并判断其是否为1，就可以得到其包含1的个数。代码实现：

思路2：

利用按位与运算符&，将该数与1进行运算，可以得知最后一位是否为1.再用位移算符>>不断地将该数的二进制位右移，以此遍历二进制的每一位。

思路3：

n=n&(n-1)每运行一次便会减少二进制中的一个1（不好想到该思路）

例如对于15,其二进制是1111，那么：

1111 - n 1110 - n-1 1110 - n 1101 - n-1 1100 - n 1011 - n-1 1000 - n 0111 - n-1 0000 - n

每运行一次便减少1，上段代码共运行了4次，所以15的二进制有4个1。按照该思路写出代码如下：

在得知n=n&(n-1)每运行一次便会减少二进制中的一个1后，我们还可以用来判断一个数是否为2的n次方，因为2的n次方在二进制中只有一个1。代码如下：

类似的，我们可以借用^异或运算符和n=n&(n-1)得到两个不同数字二进制形式下不同位数的个数