一、文章简介
本文所属专栏C语言刷题_倔强的石头106的博客-CSDN博客
注：如果没有特别说明，本文所提及的整数为有符号整型，即 int 类型
本文介绍求整数二进制位的1的个数的三种方式，三种方式在运算效率上差异不大，根据自己使用习惯和实际情况灵活运用即可
1.取模 配合 整除 的方式
这种方法的原理是利用十进制到二进制的转换过程——
- 十进制数取模2得到的余数就是二进制位的最后一位
- 再将该数除2就将二进制位去掉一位
- 循环直到该数等于0时，也就是二进制位不再含有1。统计1出现的次数
//第一种方式 #include<stdio.h> int Num1(int n) { int count = 0; while (n > 0) { if (n % 2 == 1) count++; n /= 2; } return count; } int main() { int n = 0; scanf("%d", &n); printf("%d\n", Num1(n)); return 0; }
但使用此种方式存在一定的缺陷——
当要判断的整数是负数时，循环不会进去。比如输入-1，就会得到0，这显示是不正确的
解决方法就是在函数参数使用无符号整型接收数据，这样接收到的负数就会将它看作是一个较大的整数。在这种情况下，可以看到输入-1，得到的正确结果是32
int Num1(unsigned int n)//使用无符号整型接收参数 { int count = 0; while (n > 0) { if (n % 2 == 1) count++; n /= 2; } return count; }
2.按位与 配合 右移 的方式
这种方法的原理是——
将输入的数字与1进行按位与操作，这样就可以判断最右边一位二进制位是否是1
再让输入的数字右移一位，对下一位二进制位进行判断
将上述过程放在for循环中，第一次右移0位，第二次右移1位，直到右移31位。统计1的个数，返回
#include<stdio.h> //第二种方式 int Num2(int n) { int count = 0; for (int i = 0; i < 32; i++) { if ((n >> i) & 1 == 1) count++; } return count; } int main() { int n = 0; scanf("%d", &n); printf("%d\n", Num2(n)); return 0; }
3.按位与 的方式
这种方法比较巧妙，原理是
将输入的数字 n 与n-1进行按位与操作，每次会去掉一位二进制位的1
将上述过程放在循环中进行，直到所有二进制位的1被去掉，循环结束，统计1的个数
#include<stdio.h> //第三种方式 int Num3(int n) { int count=0; while (n ) { n = n & (n - 1);//每次去掉一个二进制的1 count++; } return count; } int main() { int n = 0; scanf("%d", &n); printf("%d\n", Num3(n)); return 0; }
