求二进制中的1的个数

文章目录

• 第一种方法：模2除2
• 第二种方法：利用操作符右移后与1
• 第三种方法：该数与上比它小1的数（最优的方法）

第一种方法：模2除2

首先明白如何得到一个数的十进制的每一位？
以123为例
123%10 = 3， 123/10 = 12
12%10 = 2，12/10=1
1%10 = 1，1/10 = 0
这样就得到了一个十进制的每一位

我们可以用这个方法类推到得到一个数的二进制的的每一位
以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
顺序不重要，重要的是我们通过模2得到了三个1，说明11的二进制有三个1

以此为根据设计程序

int main()
{int n;scanf("%d", &n);int count = 0;while (n){if (n % 2 == 1) count++;n /= 2;}printf("%d\n", count);return 0;
}

但是这种方法是有缺陷的，就是不能统计负数的补码中的二进制的1的个数

第二种方法：利用操作符右移后与1

代码如下：

int main()
{int n;scanf("%d", &n);int count = 0;for (int i = 0; i < 32; i++)if ((n >> i & 1) == 1) count++;printf("%d\n", count);return 0;
}

但是这种方法也有缺陷，就是不管是什么数都必须要循环32次，效率并没有那么高

第三种方法：该数与上比它小1的数（最优的方法）

代码如下：

int main()
{int n;scanf("%d", &n);int count = 0;while (n){count++;n = n & (n - 1);}printf("%d\n", count);return 0;
}