Bitmaps and bit operations

位图

The previous articles related to bit operations are as follows,Bit operations are still very important,Because the bottom of the computer is0、1信号,So it is definitely inseparable from bit operations

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

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

How many are there in binary form of a number1

暴力递归——NQueen in detail && How to optimize with bitwise operations

XOR operation interview questions——一个数组中有一种数出现K次,其它数都出现了M次,M＞1且K＜M, 找到出现了K次的数,and requires additional space complexity of O(1),时间复杂度为O(N)

Attached is a blog explaining XOR,写得很好异或运算

此外,Some of the more difficult dynamic programs are also optimized using bitwise operations.

位图的功能

什么是位图？Bitmap is to take each bit to make a map.

具体来说,Bitmaps can be made into a collection,If the range of numbers is determined（The maximum value is determined）,Then we can use bitmaps to collect numbers,And the function that tells us whether the number is present or not.

位图的好处

能够极大的压缩空间

位图的实现（代码）

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 -> which integer
            // num % 64 -> num & 63
            bits[num >> 6] |= (1L << (num & 63));// 必须是1L,Otherwise, the number of digits is not enough,下文同理
        }

        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;
            // >>带符号右移,Complement with the most significant sign bit,If this is used here, the code will not run
            // >>>不带符号右移,最高位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--){
    
            // 让xShift right and letyShifting left essentially makes no difference,但是ywhile moving to the left,
            // May break the sign bit,会产生不可预知的错误
            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/bThe result should be the system maximum again+1
                // But the system maximum increases1无法表示,So the force buckle is mandatory in this case,返回系统最大值
                // 比如：Suppose the system minimum is -10,Then the system maximum value is 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);
        }
    }
}

力扣链接：两数相除