算法-位图与底层运算逻辑

1. 位图的理论基础

首先我们要理解什么是位图, 位图的一些作用是什么
位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在cpp中的STL中有一个bitset容器，其实就是位图法。其实就是一种为了减少空间而存在存储数字的一种数据结构
其实学习了位图之后, 我更愿意称之为"位映射"
我们基础的位图结构包含下面的几种方法

1. add方法(向位图中添加该数字)
2. remove方法(在位图中删除该数字)
3. reverse/flip方法(在位图中将该位的数字状态进行翻转)
4. contains方法(检查位图中是否有这个数字)

下面是位图存储原理的分析

位图可以存储 0 ~ n 范围内的数字, 上面线段表示每一个整数的范围, 一个整数有32个比特位, 所以一个整数可以存储32个整数的状态, 比如第一个整数存储数据的范围是[0,31],第二个是[32,63], 以此类推…, 记住这里面有一个小点就是我们a / b向上取整的代码实现是 (a + b - 1) / b
下面是基础版本位图的实现

/*** 位图是一种在指定的连续的范围上替代哈希表来存储数字数据的一种数据结构* 构造方法是传入一个数字n, 可以实现从 [0 , n - 1]范围上数字的查询(n个数字)* 数字所需的位置在 set[n / 32] , 数字的指定的位数在 n % 32 (从最右侧开始,起始为0)*/
class BitsSet {int[] set;public BitsSet(int n) {//容量需要进行向上的取整, 可以用数学工具类中的ceiling方法进行向上的取整, 也可以用这个表达式// a / b 向上取整的结果是 (a + b - 1) / bthis.set = new int[(n + 31) / 32];}/*** add方法*/public void add(int n) {set[n / 32] = set[n / 32] | (1 << (n % 32));}/*** remove方法(思考为什么用取反不用异或)*/public void remove(int n) {set[n / 32] = set[n / 32] & (~(1 << (n % 32)));}/*** reverse/flip方法(如果有这个数字就remove,如果没有就add)*/public void reverse(int n) {set[n / 32] = set[n / 32] ^ (1 << (n % 32));}/*** contains方法(检查是不是有这个数字)*/public boolean contains(int n) {return ((set[n / 32] >>> (n % 32)) & 1) == 1;}
}

2. 完整版位图实现

上面这个leetcode对位图的完整版的实现, 我们来解析一下这个位图的具体方法, 其中fix方法就是基础版本位图的add方法, unfix其实就是remove方法, flip是一个反转的方法, 可能很多人觉得真的要将位图中的所有的元素的状态都进行翻转, 其实没有必要, 而且如果全部都进行反转是十分消耗资源的, 我们直接采用一种假翻转的状态, 即定义一个布尔类型变量reverse来判断位图的元素是否进行了翻转, 反转之前我们的0代表不存在, 1代表存在, 翻转之后我们的1代表不存在, 0代表存在, 我们基本属性有set(位图的主体), one(1的个数), zero(0的个数), size(元素数量), reverse(是否进行翻转), 这里很有意思, 我们实现的filp方法直接把 reverse = !reverse , zero跟one 的数值交换即可, 就已经实现了我们的交换的目的, 其实这是一种假交换, 代码如下图所示

/*** 自己实现一个完整版本的位图*/
class Bitset {//基本的数据集合private int[] set;//数据的个数private int size;//1的个数(注意在我们这里不是真实的二进制1的个数)private int one;//0的个数(注意在我们这里不是真实的二进制0的个数)private int zero;//判断该bits是否进行了翻转private boolean reverse;public Bitset(int size) {this.size = size;set = new int[(size + 31) / 32];zero = size;one = 0;reverse = false;}public void fix(int idx) {int index = idx / 32;int bit = idx % 32;if (!reverse) {//说明没有进行翻转, 此时0表示不存在1表示存在if ((set[index] & (1 << bit)) == 0) {one++;zero--;set[index] = set[index] | (1 << bit);}} else {//此时说明已经进行了翻转操作if ((set[index] & (1 << bit)) != 0) {one++;zero--;set[index] = set[index] & (~(1 << bit));}}}public void unfix(int idx) {int index = idx / 32;int bit = idx % 32;if (!reverse) {//此时说明没有发生翻转, 此时0表示不存在1表示存在if ((set[index] & (1 << bit)) != 0) {one--;zero++;set[index] = set[index] & (~(1 << bit));}} else {if ((set[index] & (1 << bit)) == 0) {one--;zero++;set[index] = set[index] | (1 << bit);}}}public void flip() {reverse = !reverse;zero = zero ^ one;one = zero ^ one;zero = zero ^ one;}public boolean all() {return size == one;}public boolean one() {return one > 0;}public int count() {return one;}//其实就是重写一下toString方法@Overridepublic String toString() {StringBuilder sbd = new StringBuilder();int index = 0;while (index < size) {int num = set[index / 32];for (int j = 0; j < 32 && index < size; j++) {if (!reverse) {if (((num >>> j) & 1) == 1) {sbd.append(1);} else {sbd.append(0);}index++;} else {if (((num >>> j) & 1) == 1) {sbd.append(0);} else {sbd.append(1);}index++;}}}return sbd.toString();}
}

3. 底层的运算逻辑-位运算

其实计算机的底层实现加减乘除的时候是没有 + - * / 这些符号的区分的, 其实底层的运算的逻辑都是使用位运算拼接出来的…

3.1 加法

首先阐释一下加法的运算的原理就是 加法的结果 = 无进位相加的结果( ^ ) + 进位信息( & 与 << ),当进位信息为 0 的时候, 那个无尽为相加的结果, 也就是异或运算的结果就是答案

代码实现如下(不懂得看我们位运算的基础中关于异或运算的理解)

//因为是进位信息, 所以获得完了之后要左移一位
public static int add(int a, int b) {int ans = a;while (b != 0) {//ans更新为无尽无进位相加的结果ans = a ^ b;//b更新为进位信息b = (a & b) << 1;a = ans;}return ans;}

3.2 减法

减法得实现更加得简答, 就是把我们的 a - b ⇒ a + (-b), 转换为加法进行操作, 代码实现如下

/*** 生成一个数相反数的方法* 之前我们学过的那个 Brain Kernighan算法中有一个就是 -n == (~n + 1)* 所以计算相反数其实就是 add(~n , 1)*/public static int neg(int n) {return add(~n, 1);}/*** 减法的运算结果其实就是把 减法转换为加法 比如 a - b = a + (-b);*/public static int sub(int a, int b) {return add(a, neg(b));}

3.3 乘法

乘法的计算方式本质上是类比的我们小学的时候学习的竖式乘法
也就是说, 乘法的本质实现还是依赖的加法, 代码实现如下

 /*** 乘法的计算方式本质上是类比的我们小学的时候学习的竖式乘法* 也就是说, 乘法的本质实现还是依赖的加法*/public static int mul(int a, int b) {int ans = 0;while (b != 0) {if ((b & 1) == 1) {ans = add(ans, a);}//这里的b一定要是无符号右移(为了避开负数)b = b >>> 1;a = a << 1;}return ans;}

3.4 除法

首先介绍得除法的基本逻辑

位运算实现除法(基础的逻辑, 但是不完备)
这个是最特殊的位运算的题目, 因为我们要考虑除数与被除数的正负关系(全部都先转化为正数进行运算)
由于整数的第 31 位是符号位, 所以我们不进行考虑(全部处理为非负), 从30进行考虑
除法的基本逻辑就是 判断一个数里面是否包含 2^i 次方
x >= y * (2^i), 也就是x的i位是1, 反之就是0, 然后让 x - y * (2^i) ; 重复此过程直至判断到最后一位(0位)
所以代码的基本逻辑就是 x >= y << i ; 但是左移可能会溢出, 所以我们改为右移 ==> (x >> i) >= y;
还有一点就是注意这里一定要先把 a b 赋值给 x y 再进行操作, 否则可能会导致后续的 a b 值发生改变影响结果判断
代码实现如下

 public static int div(int a, int b) {//先把 a , b 处理为非负的int x = a < 0 ? neg(a) : a;int y = b < 0 ? neg(b) : b;int ans = 0;for (int i = 30; i >= 0; i = sub(i, 1)) {if ((x >> i) >= y) {ans = ans | (1 << i);//这一步为什么不会溢出其实我暂时也没懂, 先记下来吧x = sub(x, y << i);}}//注意这里的异或运算也可以作用与布尔类型, 其本质就是0 / 1进行的异或运算return a < 0 ^ b < 0 ? neg(ans) : ans;}

下面的这个才是除法的正确逻辑, 相关注释在代码中体现

下面这个才是相对完备的逻辑, 对一些特殊情况进行了处理, 因为除数与被除数有可能没有相反数(整数最小值越界)

public static final int MIN = Integer.MIN_VALUE;public static int divide(int dividend, int divisor) {//同时是最小值if (dividend == MIN && divisor == MIN) {return -1;}//同时都不是最小值(基本的除法逻辑)if (dividend != MIN && divisor != MIN) {return div(dividend, divisor);}//代码执行到这里就说明二者中必有一个是最小值, 另一个不是, 此时需要判断除数是不是-1, 判断会不会越界if(divisor == neg(1)){return Integer.MAX_VALUE;}if(divisor == MIN){return 0;}//代码走到这里就只剩下了一种情况, 就是divisor不是-1, dividend是最小值//此时你直接运算取反肯定会溢出, 所以此时进行一些变换操作, 此时(a + b)/(a - b)不会溢出//1. b为正数 ,  a / b == (a + b - b) / b ==> ((a + b) / b) - 1;//2. b为负数 ,  a / b == (a - b + b) / b ==> ((a - b) / b) + 1;dividend = add(dividend, divisor < 0 ? neg(divisor) : divisor);int ans = div(dividend,divisor);int offset = divisor > 0 ? neg(1) : 1;return add(ans,offset);}

上面除法的一些标准来源于leetcode29计算除法

谢谢观看