位运算--C语言版
问题引入
题目：求一个数字的二进制位中有多少个1
假设我们给定一个数字为7，7的二进制为0000 0111（已省略前面的24个0）接下来我们来探究一下如何求出7的二进制当中有多少个数字1
思路一
要想求出一个数字有多少个1，我首先会想到，要是能求出这个数字的每一位数字，那么不就直接知道有多少个1了，接下来的问题就是，如何求出这个数字的每一位呢？
我们知道0 & （0/1）结果都是0，只有当1&1时结果才为1，而二进制中无非就是0和1 ，所以一个数的二进制的最后一位就可以通过&1得出来
图解
image-20220427181921847
知道了一个数二进制的最后一位之后，只每次需要将这个数进行右移1位，一共右移32次，每次&1的结果为1，计数器就+1，即可统计出这个数字一共有多少个数字1
image-20220428081541051
代码如下：
public static int Findnum(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if (((n>>i)&1)==1) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(Findnum(n));
}弊端
这样子确实可以计算出一个数字的二进制的1的个数，但是7这个数字的二进制除去后面3位是1，其余都是0，也就是说在向右移位3次之后，后面就全是0了，所以之后的29次循环就是在做无用功了，所以执行效率很低
思路二
在每进入一次循环后，就将移向右移动一位的n后的n重新赋值给n，再判断n是否为为0，要是为0，就说明此时的n的二进制全是0，就可以直接返回count，这样就可以有效的不必要的减少循环次数
public static int Findnum(int n) {
int count = 0;
while (n != 0) {
if ((n& 1) == 1) {
count++;
}
n = n >> 1;
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(Findnum(n));
}完善
==但是==，要是输入的数字为负数会怎么样呢？假设输入一个-1，每右移一位数字，在二进制的左端还是会补一个符号位1，所以代码就会死循环
其实只要改成无符号右移，就会在二进制的左端补0，这样就可以解决负数的问题
public static int Findnum(int n) {
int count = 0;
while (n != 0) {
if ((n& 1) == 1) {
count++;
}
n = n >>> 1;
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(Findnum(n));
}思路三
==但是==，还能不能再优化一下？上面的代码还是在一位一位按顺序进行移位，有没有更好的方法可以将1的个数全部快速的求出来？
其实，还是有的，要是将n每次&(n-1),那么每次就会有一个1被消去，计数器统计一下即可
image-20220428082659188
这样子每次消去一个1，效率也会增加
public static int Findnum(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(Findnum(n));
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录