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計算除法

謝謝觀看