位运算--C语言版

举报
游离 发表于 2023/02/23 19:17:09 2023/02/23
【摘要】 问题引入题目:求一个数字的二进制位中有多少个1假设我们给定一个数字为7,7的二进制为0000 0111(已省略前面的24个0)接下来我们来探究一下如何求出7的二进制当中有多少个数字1思路一要想求出一个数字有多少个1,我首先会想到,要是能求出这个数字的每一位数字,那么不就直接知道有多少个1了,接下来的问题就是,如何求出这个数字的每一位呢?我们知道0 & (0/1)结果都是0,只有当1&1时结果...

问题引入

题目:求一个数字的二进制位中有多少个1

假设我们给定一个数字为7,7的二进制为0000 0111(已省略前面的24个0)接下来我们来探究一下如何求出7的二进制当中有多少个数字1

思路一

要想求出一个数字有多少个1,我首先会想到,要是能求出这个数字的每一位数字,那么不就直接知道有多少个1了,接下来的问题就是,如何求出这个数字的每一位呢?

我们知道0 & (0/1)结果都是0,只有当1&1时结果才为1,而二进制中无非就是0和1 ,所以一个数的二进制的最后一位就可以通过&1得出来

图解


知道了一个数二进制的最后一位之后,只每次需要将这个数进行右移1位,一共右移32次,每次&1的结果为1,计数器就+1,即可统计出这个数字一共有多少个数字1


代码如下:

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被消去,计数器统计一下即可


这样子每次消去一个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));
    }
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。