位图与位运算

位图

之前写过的跟位运算有关的文章如下，位运算还是蛮重要的，因为计算机底层都是0、1信号，所以肯定离不开位运算

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

一个数组中有两种数出现了奇数次，其它数都出现了偶数次，怎么找到并打印这两种数

一个数的二进制形式中有多少个1

暴力递归——N皇后详解 && 如何用位运算进行优化

异或运算面试题——一个数组中有一种数出现K次，其它数都出现了M次，M＞1且K＜M， 找到出现了K次的数，并要求额外空间复杂度为O(1)，时间复杂度为O(N)

附上一篇讲解异或的博客，写得很好异或运算

此外，一些比较难的动态规划也会用到位运算来优化。

位图的功能

什么是位图？位图就是拿每一位比特来做图。

具体来说，位图可以做出一个集合，如果数字的范围是确定的（最大值是确定的），那我们就可以用位图来实现收集数字，并且告诉我们数字存在还是不存在的功能。

位图的好处

能够极大的压缩空间

位图的实现（代码）

package com.harrison.class36;

import java.util.HashSet;

/** * @author Harrison * @create 2022-06-18-20:03 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。 */
public class Code01_BitMap1 {
    
    public static class BitMap {
    
        public long[] bits;

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

        public void add(int num) {
    
            // num>>6 -> num/64 -> 哪个整数
            // num % 64 -> num & 63
            bits[num >> 6] |= (1L << (num & 63));// 必须是1L，否则位数不够，下文同理
        }

        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("test begin");
        int max=10000;
        BitMap bitMap=new BitMap(max);
        HashSet<Integer> set=new HashSet<>();
        int testTimes=10000000;
        for(int i=0; i<testTimes; i++){
    
            int num=(int)(Math.random()*(max+1));
            double decide=Math.random();
            if(decide<0.333){
    
                bitMap.add(num);
                set.add(num);
            }else if(decide<0.666){
    
                bitMap.delete(num);
                set.remove(num);
            }else{
    
                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("test finish");
    }
}

位运算

用位运算实现加减乘除（+ - * /）

package com.harrison.class36;

/** * @author Harrison * @create 2022-06-19-8:57 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。 */
public class Code02_BitAddMinusMultiDiv {
    
    public static int add(int a, int b) {
    
        int sum = a;
        while (b != 0) {
    
            sum = a ^ b;
            b = (a & b) << 1;
            a=sum;
        }
        return sum;
    }

    public static int negNum(int n){
    
        return add(~n,1);
    }

    public static int minus(int a,int b){
    
        return add(a,negNum(b));
    }

    public static int multi(int a,int b){
    
        int res=0;
        while(b!=0){
    
            if((b&1)!=0){
    
                res=add(res,a);
            }
            a<<=1;
            // >>带符号右移，最高位符号位来补，这里如果用这个的话代码就跑不完了
            // >>>不带符号右移，最高位0来补
            b>>>=1;
        }
        return res;
    }

    public static boolean isNeg(int n){
    
        return n<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;
        for(int i=30; i>=0; i--){
    
            // 让x右移和让y左移本质上没什么区别，但是y左移的过程中，
            // 可能会突破符号位，会产生不可预知的错误
            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;
        }else if(a==Integer.MIN_VALUE){
    
            if(b==negNum(1)){
    
                // 如果a是系统最小值，b是-1，那么a/b的结果应该是系统最大值再+1
                // 但是系统最大值加1无法表示，所以力扣强行规定这种情况下，返回系统最大值
                // 比如：假设系统最小值是-10，那么系统最大值就是9
                return Integer.MAX_VALUE;
            }
            // a/b
            // (a+1)/b=c
            // a-(b*c)=d
            // d/b=e
            // c+e
            int c=div(add(a,1),b);
            return add(c,div(minus(a,multi(b,c)),b));
        }else{
    
            return div(a,b);
        }
    }
}

力扣链接：两数相除