一、题目介绍
原题链接：二进制中1的个数
二、解题思路
1. 第一种解题方法
十进制数中，例如1479，只要通过不断的%10和/10操作，就可以得到1479的每一位。
而将这个方法推广到二进制中也是可行的。只要通过不断的%2和/2操作，也可以将二进制的每一位拿出来，从而对每一位进行判断，记录1的个数。
int count_num_of_1(int n) { int count = 0; while (n) { if (n % 2 == 1) count++; n /= 2; } return count; } int main() { int num = 0; scanf("%d", &num); int ret = count_num_of_1(num); printf("%d\n", ret); return 0; }
当然，不要开心地以为到这里就完成了，当num为负数时，你会发现结果是错误的，例如num = -1。当num为-1时，num%2 != 0，因此会跳过if直接执行num /=2，结果num为0直接跳出循环并返回count=0。而真实情况下-1在内存中存储的是补码，即32个1。
不了解原码反码补码的可以看我往期博客，这里就不过多赘述。
解决方法：在count_num_of_1函数参数中将int n 改成 unsigned int n，即无符号整型。这样当num = -1时，此时n会认为num不是-1而是一个二进制全是1的数（即4294967295），此时count就为32。
2. 第二种解题方法
第二种方法是通过移位的方式求出1的个数，将二进制序列的每一位都&1，当结果为1时count++。下面以15为例子：
int count_num_of_1(unsigned int n) { int count = 0; int i = 0; for ( i = 0; i < 32; i++) { if (((n >> i) & 1) == 1) count++; } return count; }
3. 第三种解题方法
前面两种解题方法其实都不太高效，这里介绍一个非常巧妙的方法，巧妙到我们难以想象得到，该方法的核心就是n = n & (n - 1)，下面以15为例子讲解：
n = n & (n - 1)就可以理解为：只要执行一次，n的二进制序列中的1就少一个。
那么求二进制中1的个数就变成了n = n & (n - 1)能够执行几次，只要知道执行几次n = n & (n - 1)就可以知道n的二进制序列中有多少个1。
int count_num_of_1(unsigned int n) { int count = 0; while (n) { n = n & (n - 1); count++; } return count; }
这次题目的讲解就到此为止了。如果觉得作者写的不错，求给作者一个大大的点赞支持一下，你们的支持是我更新的最大动力！
