位图位运算实现加减乘除

1.位运算符号

~ 取反      ~1=0
& 按位与    1&1=1 1&0=0 0&0=0
| 按位或    1|1=1 1|0=1 0|0=0
^ 按位异或    0^0=0 1^0=1 0^1=1 1^1=0
<< 有符号左移  表示向左移动，不分正负数，低位补0
>> 有符号右移   表示向右移动，不分正负数，高位补0
>>> 无符号右移   正数和有符号右移是没有区别的，唯一有区别的时候是负数的时候，前面会补上1，而不是0

2.位图

一开始定义一个Long类型的数组，使用尽可能少的空间存储更多的数，Long类型是8个字节，一个字节是8bit,也就是说数组中每一个整数，就可以存64个数，当变成1时，表示该数存在，0时表示该数就不存在，当然所存的数时按顺序存储的，以此类推，只要知道要存入的最大值，就可以实现一个比原来数组占用空间至少小64倍的数组，这就是位图

位图实现

1.需要定义一个最大数组

 private Long[] bits;

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

2.添加数

		public void add(int num) {
//           num >> 6 -> num / 64 -> 哪个整数
//            num % 64 -> num & 63
            bits[num >> 6] |= (1L << (num & 63));
        }

删除某个数

1
2
3

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

查看某个数是否存在

1
2
3

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

整体

public class Code02_BitMap2 {

    //
    public static class BitMap {
        private 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));
        }

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

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

位运算实现加减乘除

java中加减乘除底层原理都是由位运算进行的,手写的用位运算的加减乘除是不如java的加减乘除快的，那是因为手写的还需要进行编译，但是java中的位运算是比加减乘除快的

加法实现

给俩个数a和b 例如

a=46 =>0101110

b=20=>0010100

首先ab两个数要进行无进位相加，使用按位异或^

得出

a’=0111010

再用ab两数进行&得出

b‘=0000100, 在进行左移<<

得出b’=0001000

再用a’和b’进行以上操作，直到b所有位上都是0，此时的a就是a+b的结果

public static int add(int a, int b) {
       int sum = a;
       while(b != 0) {
           sum = a ^ b;  //无进位相加信息-> sum
           b = (a & b) << 1;  //进位信息 -> b->b'
           a = sum;  //a -> a' 无进位相加信息
       }
       return sum;
   }

减法实现

减法实现的原理和加法差不多，就是需要取反一下，剩下的操作和加法一样

    public static int negNum(int n){
        return add(~n,1); //取反之后+1
}

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

乘法实现

同样也是给出两个数a和b，和小学算术题一样，需要用a每个位乘以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;
            b >>>= 1;
        }
        return res;
    }

除法实现

需要注意下，有个最小值的问题，当负数的最小值取反时，是无法取到对应的值，所以需要先将这个数加1，再进行相应的做法

//    除法
    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
        for (int i =30; i>= 0; i = minus(i,1)) {
            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)){
                return Integer.MAX_VALUE;
            }else {
                /*
                * 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(c, b)), b));
            }
        } else {
//            a / b
            return div(a, b);

（左程云视频讲解）

位图 位运算实现加减乘除