type
status
date
slug
summary
tags
category
icon
password
📝 主旨内容
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)得到两个不同数字二进制形式下不同位数的个数
- 作者:江牧
- 链接:https://lawyerjiang.top/article/practice/c/2
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章