蓝桥杯算法课【算法很美~位运算的妙用 2】学习记录

这次呢，还是通过一道例题来引出今天的学习内容

本题需要输出一个整数的二进制形式中1的个数，可能刚开始看到这道题时就会无从下手，那么如果考虑到使用位运算符中的 << 和 >>操作符是不是就简单多了，这里为大家提供了三种解题方法。

首先给大家解释一下 << 和 >> 操作符，就像它的名字一样，只需对二进制数左移和右移就可以了，那么怎么移呢

如图所示，在32个比特位表示的数中，左移之后低位补0，原来的1100 1000变为了11 0010 0000，也就是由200变为了800，不难发现左移一次，原来的数字乘以2，这个小技巧在以后的学习中也非常有用，右移也是一样的道理，只不过变为了高位补0，右边舍去，数值等于原来的数字乘以1/2。

那么明白了左移和右移之后就可以做这道题了
方法一：保持原来的数不动，用 1 去左移，再和原来的数做 & 运算。

举个栗子：

1左移之后和要比对的数字做 & 运算，如果是 1 就等于 1，记录一次。
&运算不会的可以去看上一节奥： 位运算的妙用1
方法二： 与方法一类似，这次我们选择右移要比对的数字，1 保持不动

同理，&运算之后为 1 就表示找到了一个1.

方法三： 这个方法就需要仔细的去理解，方法就是用这个数的二进制减一，如果该位置是 0 的话就需要去借位，只不过二进制借位表示的是2，
减去之后再和原来的数字做& 运算，参与借位的部分就都变为了 0 ，从而每次都消掉一个最低位的1，依次循环，直到最后结果为0，减去1的个数就是原来数字中1的个数。

将 8 减去 1 之后就变成了 7，和原来相比，原来位置的 1 变为了0，0的位置变为了1，

之后用这个数和减一之后的结果做 & 运算，那么借位的这个部分就变成了0，前面没有借位的不变

这三种方法的代码为：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个整数：");
        int num = sc.nextInt();
        //输出二进制形式
        System.out.println(Integer.toString(num, 2));
        int count1 = 0;
        //方法一
        for (int i = 0; i < 32; i++) {
            // 1 左移 32 次 ，&运算之后不等于0表示找到了一个1
            if ((num & (1 << i)) != 0) {
                count1++;
            }
        }
        System.out.println(count1);
        //方法二
        int count2 = 0;
        for (int i = 0; i < 32; i++) {
            //右移 num 和 1 做&运算，等于1就找到了一个1
            if (((num >>> i) & 1) == 1) {
                count2++;
            }
        }
        System.out.println(count2);
        //方法三
        int count3 = 0;
        while (num != 0) {
            num = (num - 1) & num;
            count3++;
        }
        System.out.println(count3);
    }

当上面讲的例题掌握之后，下面这道题就相当简单了

我们首先来思考，2的整数次方是什么，能不能相到位运算，在二进制中，2的整数次方其实也就是只有一个 1 ，想到这个之后是不是就瞬间明白了，其实也就是上面的第三个方法，只做一次减一相与判断

        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        if (((number - 1) & number) == 0) {
            System.out.println(number + "是2的整数次方");
        } else {
            System.out.println(number + "不是2的整数次方");
        }

大家可以仔细体会一下。