【C语言练习】二进制中1的个数-创新互联

• 题目详情：
• 思路一：
• 思路二：
• 思路三：

 拿到二进制的每一位，看它是否等于 1 1 1，再定义一个计数器变量，如果等于 1 1 1，计数器变量就加 1 1 1。最终计数器的值就是 1 1 1 的个数。
 现在的问题就变成了—— 如何得到二进制的每一位？ 以十进制数字 123 123 123 为例，通过123%10=3就能得到 3 3 3，不难发现：只要用一个数除以它的进制数，最终的余数就是这个数最低位上的数字，因此如果要得到 2 2 2 首先要让 2 2 2 来到最低位，只要去掉当前最低位上的 3 3 3 ， 2 2 2 就能来到最低位上。如何去掉最低位上的数字呢？ 通过123/10=13就能把最低位上的 3 3 3 去掉。可见：只要用一个数除以它的进制数，就能去掉该数当前的最后一位数字。（这里指的是整数除法）因此我们只要不断地重复上面的两个步骤，就能都得到一个数上的每一位数字。二进制数也同理。思路整理的差不多接下来就该通过代码来实现了。

代码实现：

int NumberOf1(int a)
{int count = 0;//计数器
	while (a)
	{if (a % 2 == 1)//通过取模得到最低位上的数字
		{	count++;
		}
		a /= 2;//通过整数除法取出掉最低位上的数字
	}
	return count;
}

int main()
{int a = 0;
	scanf("%d", &a);
	int num = NumberOf1(a);
	printf("%d\n", num);
	return 0;
}

上述代码缺陷：
 经过测试发现，上述代码可以准确计算出一个正整数二进制位中 1 1 1 的个数，当参数是负数时，计算出来的结果，与我们希望的结果会有很大的差距。以 − 1 -1 −1 为例，理论上 − 1 -1 −1 的补码是32个全 1 1 1 ，因此计算出来的结果应该是32才对，但上面这段代码计算出的结果是 0 0 0 ，为什么呢？结果是 0 0 0 说明if (-1 % 2 == 1)没成立过，我们可以通过内存窗口来看看-1 % 2的结果到底是什么，

 结果是ff ff ff ff。内存中存的是补码，所以对应的二进制补码就是 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111，int b说明b是一个有符号的的整型，因此前面二进制的最高位是符号位，并且是 1 1 1 ，说明-1%2的结果是一个负数，自然就不可能等于 1 1 1 了。我们发现：只要是一个负数，对 2 2 2 取模得到的结果就一定是一个负数，就永远也不可能等于 1 1 1，如何解决这个问题呢？
 这里我们可以把形参设置成一个无符号的整型变量，此时问题就迎刃而解了。还是以 − 1 -1 −1 为例： − 1 -1 −1 在内存中的补码是 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111 传参的时候用一个无符号的整型变量a去接收 ，在这个无符号的整型变量a的眼里 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111 就不再是什么 − 1 -1 −1 的补码了，a认为这就是一串普普通通的二进制代码，没有什么所谓的符号位这些乱七八糟的东西。因此再用a%2得到的结果就不再可能是负数了，我们还是可以通过调试来一探究竟。

 上图中，我们把 − 1 -1 −1 赋值给一个无符号的的整型变量a，然后用a%2得到的结果是 1 1 1 ，并且也是无符号整型；用a/2得到 2147483647 2147483647 2147483647 ，这个很容易理解，因为 − 1 -1 −1 的补码 11111111111111111111111111111111 11111111111111111111111111111111 11111111111111111111111111111111 在a的眼里就是一个平平无奇的二进制序列，没有符号位，这个二进制序列转换成十进制就是： 4 , 294 , 967 , 295 4,294,967,295 4,294,967,295，除以 2 2 2 就得到 2147483647 2147483647 2147483647

代码修改：

int NumberOf1(unsigned int a)//把形参改成无符号整型，就对负数也适用了
{int count = 0;
	while (a)
	{if (a % 2 == 1)
		{	count++;
		}
		a /= 2;
	}
	return count;
}

int main()
{int a = 0;
	scanf("%d", &a);
	int num = NumberOf1(a);
	printf("%d\n", num);
	return 0;
}

 上面的代码，在传 − 1 -1 −1 的时候，计算出来的结果就是我们所期待的 32 32 32 了。到这里，思路一就结束了。接下来看另一种思路。

 思路二的大体方向和思路一 一样，得到二进制序列的每一位，然后看其是否等于 1 1 1 。只不过思路二的实现方法与思路一不同，会比思路一容易一些，都是初学者不容易想出来。接下来就来整理一下思路二吧，首先我们还是希望得到二进制的每一位，此时我们可以借助按位与（&)这个操作符来实现，还记得按位与的计算过程嘛？对应的两个二进制位都为 1 1 1 的时候出 1 1 1 ，其他全部出 0 0 0 ，因此，可以让待求得二进制序列按位与上 1 1 1 , 1 1 1 的二进制序列为 00000000000000000000000000000001 00000000000000000000000000000001 00000000000000000000000000000001 ，此时待求的二进制序列的最低位如果是 1 1 1 ，那1&1得到的结果就是 1 1 1 ，如果待求的二进制序列的最低位是 0 0 0 ，那0&1得到的结果就是 0 0 0，我们发现任何一个二进制只要与上 1 1 1 都会得到它自身。此时我们得到了二进制序列的最低位，那它的第二位、第三位、第四位……呢？别忘了，我们还有一个移位操作符，我们可以利用移位操作符，让二进制序列往右移动，使得每一个二进制位都能与上 1 1 1 ，这样我们就能拿到二进制序列的每一位了。大体思路捋的差不多了，接下来该上代码了。

int NumberOf1(int a)
{int i = 0;
	int count = 0;
	for (i = 0; i< 32; i++)//最多只需右移31个二进制位
	{if (((a >>i) & 1) == 1)//只有当1 & 1结果才是1，让a的二进制位一直右移
		{	count++;
		}
	}
	return count;
}

int main()
{int a = 0;
	scanf("%d", &a);
	int num = NumberOf1(a);
	printf("%d\n", num);
	return 0;
}

 思路二也无需考虑什么正负数，因为移位操作符和位操作符都是直接针对二进制位来计算的，看完思路二我就只想说妙。但是别急，接下来的思路三才算得上是“王炸”

 这里直接上方法，记住下面这个式子：n=n&(n-1)。举个例子，以十进制的 11 11 11 为例， 11 11 11 的二进制是 1011 1011 1011 ，此时n=1011;，n-1=1010;，n&(n-1)=1010此时n就变成了： 1010 1010 1010 ，对比前面的n我们发现二进制序列最右边的 1 1 1 变成了 0 0 0 ，接着往下，n=1010;，n-1=1001;，n&(n-1)=1000此时n就变成了 1000 1000 1000 对比第二个n二进制序列最右边的 1 1 1 又变成了 0 0 0，再往下看，n=1000;，n-1=0111;，n&(n-1)=0000此时n就变成了 0000 0000 0000 。不难发现：n从最初的 1011 1011 1011 ，变成了现在的 0000 0000 0000 是把n=n&(n-1)这个式子执行了 3 3 3 次，什么？3？？这不就是 1011 1011 1011 这个二进制序列里面 1 1 1 的个数嘛，其实这并非偶然，因为n=n&(n-1)这个式子每执行一次，就会把当前n这个二进制序列里面最右边的 1 1 1 去除掉，直到整个二进制序列变成 0 0 0 ，分析的差不多了，接下来上代码！

int NumberOf1(int n)
{int count = 0;
	while (n)//能变成全0的时候，就不用再执行下面的式子了
	{n = n & (n - 1);
		count++;//记录上面这个式子一共执行了多少次
	}
	return count;
}

int main()
{int n = 0;
	scanf("%d", &n);
	int num = NumberOf1(n);
	printf("%d\n", num);
	return 0;
}

 哈哈，没骗你吧，思路三才是最终的“王炸”

 好了，这道题的分享就到这里啦，如果你有更好的思路或者方法，欢迎在评论区或者私信，给我留言，拜拜咯！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧