7、位运算，位图

标签：return 运算 int res num 64 public

1、位运算

顾名思义，位运算符作用于位，是逐位进行操作。最常用的有：与 &、或 |、异或 ^。
对于基本的位运算，我们有一个常用的口诀：

1.按位与 &：遇0则0
2.按位或 |：遇1则1
3.按位异或 ^ ：相同为0，相异为1
4.左移 <<: a << n，相当于 a * 2^n
5.带符号右移 >>: a >> n，相当于 a / 2^n，用符号位补齐
6.无符号右移 >>>: a >>> n，用0补齐

1.1、正负数表示

正数的符号位为0
负数的符号位为1

1.2、补码

负数 = 其绝对值取反加一，例如：-2
2： 0000 0010
~2：1111 1101
+1：1111 1110
利用补码，负数就没有了，从而就把“减法转换为加法运算”，利用这个特点，计算机中，仅需一个“加法器”，就够用了。

1.3、打印一个整数的 32 位信息

public class BitOperation {
    public static void print(int num) {
        for (int i = 31; i >= 0; i--) {
            System.out.print((num & (1 << i)) == 0 ? "0" : "1");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 00000000000000000000000001000000
        print(64);
    }
}

2、位图的功能

使用二进制位来保存信息
以long[]数组为例，long 类型8个字节，64位
num % 64 相当于num & 63，但是&的效率 > %的
因为：7个二进制位可以表示0~63共64个数
所以：舍弃掉7位以上的高位，剩下的数即为 mod
num % 64，相当于num & 63

3、位图的实现

添加数据使用逻辑或 |，删除/查找数据使用逻辑与 &
例：第二位要保存数据，则原数据 | (1L << 2)
0 1 1 0 1 0 1 0
0 0 0 0 0 1 0 0 ->（1L << 2）
结果:0 1 1 0 1 1 1 0

点击查看代码

public class BitMap2 {

    public static class BitMap {
        private long[] bits;

        /**
         * 右移 >> 6 位相当于除以 2的6次方
         * + 64，是防止 max < 64的情况
         * 一个long类型，8个字节，64位
         *
         * @param max 最大整数
         */
        public BitMap(int max) {
            this.bits = new long[(max + 64) >> 6];
        }

        /**
         * num >> 64 -> num / 64 -> num存放在第几个整数里
         * num % 64 -> num & 63
         * 使用逻辑或 |，将数据写入
         * 0 0 0 0 0，例如找到数据要保存在第2位
         * 0 0 1 0 0，| 逻辑或，则将数据存入
         *
         * @param num 保存在位图中的数
         */
        public void add(int num) {
            bits[num >> 6] |= (1L << (num & 63));
        }

        public void delete(int num) {
            bits[num >> 6] &= ~(1L << (num & 63));
        }

        public boolean contains(int num) {
            return (bits[num >> 6] & (1L << (num & 63))) != 0;
        }
    }

    public static void main(String[] args) {
        System.out.println("测试开始");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            int num = (int) (Math.random() * max);
            double decide = Math.random();
            if (decide < 0.33) {
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.66) {
                bitMap.delete(num);
                set.remove(num);
            } else {
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("contains error");
                    break;
                }
            }
        }

        for (int num = 0; num < max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("contains error");
                break;
            }
        }
        System.out.println("测试结束");
    }
}

3、使用位运算进行加减乘除

3.1、加法：进位和 + 无进位和

a,b无进位相加，相当于按位异或 a ^ b
a + b进位信息，相当于按位与之后左移一位(a & b) << 1
重复上述步骤，直到进位为0时的 a' ^ b'即为 a + b

3.2、减法

a - b相当于，a加上，b的相反数 a - b -> a + (-b)
b的相反数为，b按位取反加一，~b + 1

3.3、乘法

a * b 使用二进制计算
1.判断（b & 1）是否为 0，不为0则将结果加入
2.a 左移一位 a << 1
3.b 无符号右移一位 b >>> 1
4.当b==0时，返回 res，即为 a * b

3.4、除法

a / b = c

a减去 b << n位后不大于a的数，此时商1
不够减商 0
重复上述步骤，直到 b << 0位即结果
b << 可能会越界，我们使用 a >>
例如101100101除以111：

测试链接：https://leetcode.com/problems/divide-two-integers

3.5、代码实现