前言

求二进制中1的个数

1、第一种思路：n & 1

对于任何一个数n和1按位与都会得到n的个位是不是1，其他位都会和0相与得0。
个位是0，表达式n&1的结果是0，个位是1，结果也是1.

那么问题就来了这只能判断个位呀，要是判断其他位怎么整呀？？

不慌这里我们用移位操作符<<和>>

1.对1左移

每一次判断一位之后把数字1左移一位

左移代码

int com_binary1(int n)//和1按位与  移动1
{
	int count = 0;
	int f = 1;
	while(f)
	{
		if(n & f)
			count++;
		f <<= 1;
		
	}
	return count;
}

2.把n右移

判断完的位所对应的数可以丢弃直接右移

右移代码

int com_binary(int n)//和1按位与  移动n
{
	int count = 0;
	while (n)
	{
		count += n & 1;
		n >>= 1;
	}
	return count;
}

右移缺陷

大部分编译器都是逻辑右移，那么很容易想到对于输入一个负数每一次左移都会在最高位补1，那么最终就变成

0xFFFFFFFF

永远大于0，从而陷入死循环

2种改进代码

一、对于32位平台每个数据保存32位，可以控制移位次数来避免死循环

int com_binary(int n)//和1按位与  移动n
{
	int count = 0;
	for (int i=0;i < 32;i++)
	{
		count += (n>>i) & 1;
	}
	return count;
}

二、改变传进来的值类型为unsigned int
我们知道数据在计算机中存储的是补码，数据的正负主要看你读取的形式。
因此我们可以把形参类型改为unsigned int 直接把传进来的数据转为无符号整形

int com_binary(unsigned int n)//和1按位与  移动n
{
	int count = 0;
	while (n)
	{
		count += n & 1;
		n >>= 1;
	}
	return count;
}

2、第二种思路：n % 2

对于二进制来说从右往左每一位分别代表2的0次方，2的1次方…从第二位开始都是2的整数倍，只有第一位不是1就是0.所以n % 2正好是第一位的数字。
那么同理数据左移相当于把该数字 * 2，右移相当于 / 2.

因此就可以每一次先 % 2，之后 / 2；

代码

int com_binary3(unsigned int n)//模2除2
{
	int count = 0;
	while (n)
	{
		count += n % 2;
		n /= 2;
	}
	
	return count;
}

同理这种解法对于负数也会陷入死循环中，需要把接收来的数据转化为无符号

3、第三种思路：n & (n-1) (最容易想不到的)

通过以上的例子可以看出n = n & n-1会把二进制中最右侧的1变成0！！！！！！

代码

int com_binary4(int n)//n&n-1
{
	int count = 0;
	while (n)
	{
		n= n & (n - 1);
		count++;
	}

	return count;
}

这种解法非常巧妙！！！