位运算--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));
}