03-位图

1. BitMap

• 一个数在BitMap是否存在

/**
 * 位图
 * 集合太占用空间，存一个数占用4字节
 */
public class _01_BitMap {

    // 这个类的实现是正确的
    public static class BitMap {
        // long 8字节，64位
        private final long[] bits;

        /**
         * BitMap
         */
        public BitMap(int max) {
            // (max + 64) >> 6  ->  (max + 64) / 64
            bits = new long[(max + 64) >> 6];
        }

        public void add(int num) {
            // **出错啦！！！1是4字节，32位。1L是8字节，64位**
            // num >> 6 -> num / 64 -> 哪个整数
            // num % 64 -> num & 63
            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 = 10_000;
        BitMap bitMap = new BitMap(max);
        // hash表
        HashSet<Integer> set = new HashSet<>();
        int testTime = 10_000_000;
        for (int i = 0; i < testTime; i++) {
            int num = (int) (Math.random() * (max + 1));
            double decide = Math.random();
            if (decide < 0.333) {           // 1/3概率加一个数
                bitMap.add(num);
                set.add(num);
            } else if (decide < 0.666) {    // 1/3概率删一个数
                bitMap.delete(num);
                set.remove(num);
            } else {                        // 1/3概率查一个数
                if (bitMap.contains(num) != set.contains(num)) {
                    System.out.println("Oops!");
                    break;
                }
            }
        }
        // 全查一遍，比对
        for (int num = 0; num <= max; num++) {
            if (bitMap.contains(num) != set.contains(num)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }

}

2. 加-减-乘-除

• (2 + 6) => (0 1 1 0) + (0 0 1 0)
  • a ^ b => 无进位相加
  • (a & b) << 1 => 进位信息

/**
 * 位运算（int） + - * /
 * https://leetcode.com/problems/divide-two-integers
 */
public class _02_BitAddMinusMultiDiv {

    /**
     * (a + b)原理
     * 位运算不能出现 + 号，因此把b递归为0
     * <p>
     * 0 1 1 0
     * 0 0 1 0
     * ----------------
     * 0 1 0 0
     * 0 1 0 0
     * ----------------
     * 0 0 0 0
     * 1 0 0 0
     * ----------------
     * 1 0 0 0
     * 0 0 0 0
     */
    public static int add(int a, int b) {
        int sum = a;
        // 什么进位信息为0，a即为结果
        while (b != 0) {
            sum = a ^ b;        // 无进位相加
            b = (a & b) << 1;   // 进位
            a = sum;
        }
        return sum;
    }

    /**
     * (-a)原理
     */
    public static int negNum(int n) {
        return add(~n, 1);
    }

    /**
     * (a - b)原理
     */
    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    /**
     * (a * b)原理。支持负数，原理相对复杂（略）
     * 竖式运算
     * 支持负数
     * <p>
     * 0 0 0 1 1 0
     * 0 0 0 1 1 1
     * ----------------
     * 0 0 0 1 1 0
     * 0 0 1 1 0
     * 0 1 1 0
     * ----------------
     * 0 1 1 1 1 0
     */
    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

    /**
     * negative
     * 判断是否是负数
     */
    public static boolean isNeg(int n) {
        return n < 0;
    }

    /**
     * div
     * <p>
     * 0 1 1 1 1 0
     * 0 0 0 1 1 1
     * <p>
     * ----------------
     * 0 1 1 1 0 0
     * 0 0 0 0 1 0
     */
    public static int div(int a, int b) {
        // 负数 -> 正数 => 取绝对值
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        // x, y一定是非负的。31位是符号位，从30位即可
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            // x右移，避免右移超范围
            if ((x >> i) >= y) {
                res |= (1 << i);
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    /**
     * 除法（考虑系统最小值）
     */
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            return 0;
        }
        // a为系统最小
        else if (a == Integer.MIN_VALUE) {
            // a/-1
            if (b == negNum(1)) {
                // LeetCode强行规定，最小值的相反数为最大值
                return Integer.MAX_VALUE;
            } else {
                // 1. c = (a+1) / b
                // 2. c + (a - c*b) / b
                int c = div(add(a, 1), b);
                return add(c, div(minus(a, multi(c, b)), b));
            }
        }
        // 都不是系统最小
        else {
            return div(a, b);
        }
    }

}