位運算、位圖

位運算

基本位運算

列舉幾個有關位運算的常識（常用或是簡單易混）：

1. >>：算術右移，右移后左端補符號位；>>>邏輯右移，右移后左端補0

2. 位運算取相反數：~num + 1。int、long類型的最小值的相反數還是自己，這是由它們的取值范圍決定的

3. 打印一個二進制數（int為例）：

       public static void printBinary1(int num) {for(int i = 31; i >= 0; i--) {System.out.print((num & (1 << i)) == 0 ? 0 : 1);}}
   

   具體式子有很多，關鍵是理解，再比如：

       public static void printBinary2(int num) {for(int i = 31; i >= 0; i--) {System.out.print((num >> i) & 1);}}
   

---

異或運算

異或運算的性質：

1. 異或運算就是無進位相加
2. 異或運算滿足交換律、結合律（不論異或順序是什么，同一批數字的異或和不變）
3. 0 ^ n = n、n ^ n = 0
4. 整體異或和為x，其中一部分的異或和是y，則剩下部分的異或和為x ^ y

---

交換兩個數

不使用第三個變量，交換兩個數：

        int a = 10;int b = 5;a = a ^ b;//a: a ^ b  b: bb = a ^ b;//b = a ^ b ^ b = a   a = a ^ ba = a ^ b;//a = a ^ b ^ a = bSystem.out.println(a);System.out.println(b);

• 如表格：

語句	a	b
a = a ^ b	a ^ b	b
b = a ^ b	a ^ b	a（a ^ b ^ b）
a = a ^ b	b（a ^ b ^ a）	a

---

無比較返回最大值

這是一個看起來比較繞但是很高效的實現：

    /*** 將負數返回1，非負返回0  => 負數返回0，非負返回1* @param n* @return*/public static int flip(int n) {//翻轉，0變1，1變0return n ^ 1;}public static int sign(int n) {//拿到翻轉后的符號位，使得1表示非負，0表示負數return flip(n >>> 31);}/*** 有溢出風險* c 可能溢出* @param a* @param b* @return*/public static int getMax1(int a, int b) {int c = a - b;int returnA = sign(c);int returnB = flip(returnA);//returnA和returnB一定是相反的return a * returnA + b * returnB;}/*** 無溢出風險* @param a* @param b* @return*/public static int getMax2(int a, int b) {int c = a - b;//此時c可能溢出，可能不溢出//a、b、c的符號int sa = sign(a);int sb = sign(b);int sc = sign(c);int diffAB = sa ^ sb;//判斷a、b的符號是否一樣int sameAB = flip(diffAB);int returnA = sa * diffAB + sc * sameAB;int returnB = flip(returnA);return a * returnA + b * returnB;}

• 解釋有溢出風險的實現：c變量存儲a - b的差值，returnA拿到c的符號位，c為非負數返回1，否則返回0,；returnB是returnA翻轉。

  a * returnA + b * returnB：如果a大，則c變量存儲的是正數，returnA經sign(c)拿到的就是1，returnB拿到的是0，代入式子可知返回值就是a；b大的情況同理可知。

• 然而int c = a - b存在溢出風險，使得c的值是一個不準確的值，例如：當a是一個較大的正數，b是一個較大的負數的情況，就很容易發生溢出。

  解釋無溢出風險的實現：仍然先計算a - b，結果存在c中，此時c是否因溢出而不準確無法確定；拿到a、b、c三個數的符號；diffAB = sa ^ sb，即當a和b符號相同，diffAB存儲0，相反存儲1，sameAB是diffAB的翻轉

  returnA = sa * diffAB + sc * sameAB：

  returnA == 1當且僅當sa == 1 && diffAB == 1或sc == 1 && sameAB == 1。sa == 1 && diffAB == 1：a和b符號不同，a為正數，b為負數，a > b最終返回a；sc == 1 && sameAB == 1：a和b符號相同（不會發生溢出），c為正數，a > b最終返回a。

  最終return a * returnA + b * returnB;符合預期。

---

缺失的數字

原題鏈接：面試題 17.04. 消失的數字 - 力扣（LeetCode）

---

這道題目用到 整體異或和為x，其中一部分的異或和是y，則剩下部分的異或和為x ^ y 這個性質（結論），0~n就是整體，所給數組就是部分，對兩個集合分別求得異或和，然后再異或得到的結果就是缺失的數字。

之所以這么容易，也是因為只缺失了一個數字。

---

【代碼實現】

class Solution {public int missingNumber(int[] nums) {int xorSum = 0;int numSum = 0;for(int i = 0; i < nums.length; i++) {xorSum ^= i;numSum ^= nums[i];}xorSum ^= nums.length;return xorSum ^ numSum;}
}

---

唯一出現奇數次的數

給定一個數組，其中只有一個數只出現了奇數次，求這個數。

很簡單，只需要將數組的所有元素異或得到的異或和就是所求數字。因為出現偶數次的數都兩兩相消成0了，因此最終剩下的就是唯一出現奇數次的數。

---

測試鏈接：136. 只出現一次的數字 - 力扣（LeetCode）

class Solution {public int singleNumber(int[] nums) {int xorSum = 0;for(int num : nums) {xorSum ^= num;}   return xorSum;}
}

• 這道題目只是其中一種情況，出現1次就是奇數次，2次就是偶數次。

---

唯二出現奇數次的數

提取二進制狀態中最右側的1：

這是 Brian Kernighan算法 的關鍵部分，具體做法其實很簡單：

假設要提取n的二進制狀態中最右側的1，只需要 n & (~n + 1)，等價于 n & (-n)。

簡單用8位驗證一下：

表達式	結果
n	0010 1010
~n	1101 0101
~n + 1	1101 0110
n & (~n + 1)	0000 0010

思路：假設唯二出現奇數次的數為a和b

先求所有數的異或和，存放到假設eor1中，則eor1 = a ^ b（出現偶數次的都兩兩相消了）；既然a和b是不相等的數，那么a ^ b的表示的二進制狀態中一定存在 1，為 1 的位上對應a和b的狀態一定是相反的（一個是1一個是0），利用上面提到的算法可以得到最右側的1的狀態，然后根據這一位上的狀態可以將原數組的數分為兩部分，一部分數的這一位是1；另一部分數的這一位是0，a和b一定不在同一個部分， 然后再次遍歷原數組，只將這一位為1（當然為0也可以）的數字異或起來得到一個異或和放到假設eor2中，則eor2一定是a、b的其中一個（因為偶數次的數字還是會相消），然后另一個為eor1 ^ eor2（eor1 = a ^ b，假設eor2 = a，則b = eor1 ^ eor2；同理，如果eor2 = b，a = eor1 ^ eor2）

---

測試鏈接：260. 只出現一次的數字 III - 力扣（LeetCode）

class Solution {public int[] singleNumber(int[] nums) {int eor1 = 0;int eor2 = 0;for(int num : nums) {eor1 ^= num;}//eor1 = a ^ bint tmp = eor1 & (-eor1);for(int num : nums) {if((num & tmp) != 0) {eor2 ^= num;}}return new int[]{eor2, eor1 ^ eor2};}
}

• 這道題目仍然是一種前面介紹的其中一種情況。

---

唯一出現次數少于m次的數

思路：維護一組記錄，記錄了遍歷完所有數后，每一位上1出現的次數。如果某個記錄代表的位上的1出現的次數 % m != 0，就代表這一位上1的次數曾經因為 出現次數少于m次的那個數 的出現而不再是m的整數倍，即要尋找的數的這一位上一定是1（如果是0的話就不會影響1出現次數的統計，也就能保證是m的整數倍了），我們只需要將每條這樣的記錄對應的位設置為1，得到的狀態對應的數就是結果。

    public int singleNumber(int[] nums, int m) {int[] cnts = new int[32];for(int num : nums) {for(int i = 0; i < 32; i++) {cnts[i] += num >> i & 1;}}int ans = 0;for(int i = 0; i < 32; i++) {if(cnts[i] % m != 0) {ans |= 1 << i;}}return ans;}

---

測試鏈接：137. 只出現一次的數字 II - 力扣（LeetCode）

class Solution {public int singleNumber(int[] nums) {int[] cnts = new int[32];for(int num : nums) {for(int i = 0; i < 32; i++) {cnts[i] += num >> i & 1;}}int ans = 0;for(int i = 0; i < 32; i++) {if(cnts[i] % 3 != 0) {ans |= 1 << i;}}return ans;}
}

• 這道題目也是前面介紹的其中的一種情況，之前介紹的兼顧這道測試題目。
• 問題記錄：對于cnts[i] += num >> i & 1，不要誤寫成cnts[i] += num & (1 << i)，前者的num >> i & 1的結果集只有0和1，而后者num & (1 << i)的結果要么是 0，要么是2 ^ i，而我們只希望判斷每個數每一個位是否是1而對相應的數組位置的值累加一次即可。

---

位運算進階

判斷一個整數是不是2的冪

一個是2的冪的整數有什么特點？它的二進制表示中只有一個位上的數字為1，因此，只需要利用 Brian Kernighan算法 拿到最左側的1的狀態，看這個狀態的數值是否等于待檢驗整數即可。

---

測試鏈接：231. 2 的冪 - 力扣（LeetCode）

class Solution {public boolean isPowerOfTwo(int n) {return n > 0 && (n & -n) == n;}
}

• 當然2的冪一定是大于0的。

---

判斷一個整數是不是3的冪

一個數是3的某次冪，則這個數一定只含有3這個質數因子。（質數因子是指一個數的因子中是質數的那些因子；質數是只能被1和它本身整除的大于1的整數；因子（因數）是指能夠整除一個給定整數的數）

可以通過以下步驟來證明這個結論：

1. 假設一個數字 n 是3的某次冪，即 n = 3 ^k，其中 k 是一個非負整數。
2. 根據質數的定義，3是一個質數，它只有1和3兩個正因數。
3. 當我們計算 3 ^k 時，我們實際上是在將3這個質數乘以自己 k 次。因此， 3 ^k 的所有質數因子都是3。
4. 由于 n=3 ^k，所以 n 的所有質數因子也都是3。這意味著 n 只含有3這個質數因子。

1162261467（3^19）是整形int范圍內最大的3的冪，只含有3這個質數因子，那么如果一個數 n 也只含有3這個質數因子，則有1162261467 % n == 0；反之，1162261467 % n != 0

---

測試鏈接：326. 3 的冪 - 力扣（LeetCode）

class Solution {public boolean isPowerOfThree(int n) {return n > 0 && 1162261467 % n == 0;}
}

---

大于等于n的最小的2的冪

假設n為33，則返回64，因為32不滿足大于等于的條件。這個算法的具體實現為：

    public static final int nearTwoPower(int n) {if (n <= 0) {return 1;}n--;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;return n + 1;}

• 方法一開始的if語句很好理解，即如果n的值小于等于0，假設-5，則大于等于-5的最小的2的冪一定是1。

• n--的作用是確保當n的值就是2的冪時，能夠返回n。如果沒有這個語句，經過下面的邏輯后將會返回較大的2的冪，比如當n = 8時，如果沒有提前n--，則最后返回的值將是16，這顯然不符合預期。

• n--和return語句之間的邏輯總結起來就是將 n 的二進制表示“擴展”到一個從最高位的 1 到最低位全為 1 的狀態（刷為1）。

  表格演示n == 37時的轉換過程：

  操作	操作后n的狀態（方便起見，僅展示最低的8位）
  n	0010 0101（37）
  n--	0010 0100
  `n	= n >>> 1`
  `n	= n >>> 2`
  `n	= n >>> 4`
  `n	= n >>> 8`
  `n	= n >>> 16`
  n + 1	0100 0000（64）

---

這是一個實踐性很強的算法，當我們查看Java 8的源碼時，會發現這個算法的存在，具體操作如下圖：

---

[left, right]內所有數字&的結果

測試鏈接：201. 數字范圍按位與 - 力扣（LeetCode）

---

這個問題可以由下面的算法快速解決：

class Solution {public int rangeBitwiseAnd(int left, int right) {while(left < right) {right -= right & (-right);}return right;}
}

• 如果left == right則意味著只有一個元素，此時不會進入循環直接返回right是符合預期的
• 如果left < right則意味著：right - 1也一定在計算范圍內，那么有什么用呢？
  1. 有：所有的與項的某一位都是1，最終結果的這一位才會是1
  2. right - 1即right的二進制表示的最右側的1變為0，前面提到right - 1一定在計算范圍內，則最終結果對應的right最右側1的那個位上一定為0，因此right減去最右側的1，然后繼續判斷left和right是否相等。
  3. 每次循環，right 的二進制表示中最低位的 1 都會被變成 0。這相當于逐步“縮小” right 的值，直到 left 和 right 相等。此時，right 的值就是從 left 到 right（包括 left 和 right）的所有整數的按位與的結果。

---

反轉一個二進制狀態

反轉一個二進制狀態即二進制狀態逆序，例如（四位舉例）1101變為1011，大佬想出了一個高效的算法，這個算法不需要條件判斷，十分高效：

	public static int reverseBits(int n) {n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);n = (n >>> 16) | (n << 16);return n;}

單看代碼十分抽象，我們一點一點理解：

首先，大佬的整體思路是這樣的：先一位一位的換，然后兩位兩位的換，接著四位四位的換，八位八位的換，最終十六位十六位的換，經過這樣的多番輪換，最終就能逆序二進制。以8位二進制為例（與32位原理一致，只不過換完4v4那一輪即可）：

操作	此時的狀態
無任何操作	1000 0101
1v1交換	0100 1010
2v2交換	0001 1010
4v4交換	1010 0001

• 結果顯然正確，對于32位來說，拓展到16v16交換即可。

---

基本思路了解了，與代碼有什么關系呢？

我們仍然假設一個8位的二進制為：abcd efgh：

先模擬1v1交換：

• 首先計算(abcd efgh) & (1010 1010) ，結果1對應的位信息會被留下來，0對應的位都變為0，得到a0c0 e0g0，然后將結果右移1位，得到0a0c 0e0g

• 然后計算(abcd efgh) & (0101 0101)，結果1對應的位信息會被留下來，0對應的位都變為0，得到0b0d 0f0h，然后將結果左移一位，得到b0d0 f0h0

• 然后將上面兩步的最終結果|起來，即(0a0c 0e0g) | (b0d0 f0h0)，得到badc fehg，此時就完成了1v1的交換

  我們知道，二進制的4位代表十六進制的1位，1010 1010轉化為十六進制就是aa；0101 0101轉化為十六進制就是55，我們是以8位二進制為例，因此對于32位的二進制完成1v1交換，需要的就是代碼中的0xaaaaaaaa和0x55555555

同理，接著實現2v2的交換：

• 首先計算(badc fehg) & (1100 1100)，得到ba00 fe00，然后將結果右移2位，得到00ba 00fe

• 然后計算(badc fehg) & (0011 0011)，得到00dc 00hg，然后將結果左移2位，得到dc00 hg00

• 將上面兩步的結果|起來，即(00ba 00fe) | (dc00 hg00)，得到dcba hgfe，此時就完成了2v2的交換

  1100 1100轉化為十六進制就是cc，0011 0011轉化為十六進制就是33，此時再看代碼就知道怎么回事了

后續是同樣的道理，自己下來可以舉一個32位的例子驗證一下。

---

測試鏈接：190. 顛倒二進制位 - 力扣（LeetCode）

public class Solution {public static int reverseBits(int n) {n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);n = (n >>> 16) | (n << 16);return n;}
}

---

返回一個數二進制中有幾個1

題意很好理解，像1010 1000就返回3，但是大佬又想到了一個高效的方法，不需要循環：

    public static int cntOnes(int n) {n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);return n;}

這個算法的基本思想：

1. 分組統計：將整數的二進制表示分成若干組，每組統計 1 的數量。
2. 合并統計：將相鄰的組合并，統計更大的范圍內的 1 的數量。
3. 逐步擴展：重復上述過程，直到統計完整個整數。

---

仍然以8位二進制舉例：0000 1101

• 初始狀態0000 1101，每一位算一個組，每組的數字就表示這一組中1的數量，顯然此時分了8組，每一組1的數量就是每一組位上的數字。

• 接著執行n = (n & 0x55555555) + ((n >>> 1) & 0x55555555)：

  1. n & 0x55555555：提取偶數位。
     • 0000 1101 & 0101 0101 = 0000 0101
  2. (n >>> 1) & 0x55555555：提取奇數位并右移一位。
     • 0000 1101 >>> 1 = 0000 0110
     • 0000 0110 & 0101 0101 = 0000 0100
  3. 將兩者相加：
     • 0000 0101 + 0000 0100 = 0000 1001

  這一步的結果：0000 1001，每兩位算一個組，每組的數字就表示這一組中1的數量，此時分了4組：00、00、10、01，每一組對應的1的個數：0、0、2、1

• 接著執行n = (n & 0x33333333) + ((n >>> 2) & 0x33333333)：

  1. n & 0x33333333：提取第0、1位和第4、5位。
     • 0000 1001 & 0011 0011 = 0000 0001
  2. (n >>> 2) & 0x33333333：提取第2、3位和第6、7位，并右移兩位。
     • 0000 1001 >>> 2 = 0000 0010
     • 0000 0010 & 0011 0011 = 0000 0010
  3. 將兩者相加：
     • 0000 0001 + 0000 0010 = 0000 0011

  結果：0000 0011，每四位分一組，顯然分了2組：0000、0011，每一組對應的1的個數：0、3

• 依次類推，拓展到8位為一組，如果是32位就逐步拓展到32位為一組，最后的值就是所有的1的數量。

---

測試鏈接：461. 漢明距離 - 力扣（LeetCode）

class Solution {public int hammingDistance(int x, int y) {int n = x ^ y;n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);return n;}
}

• 這道題目沒有直接說計算位為1的數量，而是提供了一個場景，利用異或運算的特性一轉換再代入算法即可。

---

后面幾個案例的代碼的確很抽象，很強但似乎太得瑟了，其實不是的，這些代碼是有現實意義的，因為：條件判斷相比于賦值、位運算、算術運算是稍慢的，但是自己寫算法時不需要追求不寫條件判斷，那樣只會給自己找麻煩，至于大佬的實現欣賞并理解就好，下次直接當模板使用。

? ——左程云

---

位圖

概念及實現

位圖即用每一位來存放某種狀態，適用于海量數據，整數，數據無重復的場景，通常是用來判斷某個數據是否存在的。

騰訊曾經有一道面試題：給40億個不重復的無符號整數，無序。快速判斷一個無符號整數是否在這40億個數中。

分析：如果遍歷，時間復雜度為O(N)；如果先排序后二分，時間復雜度為O(N*logN + logN)。

先拋開時間不談，我們不能忽略一點，就是存儲問題，10億個字節大約是1G，假設就用int類型存，10億個整數大約是4G，40億整數大概是16G，這是一個很大的數字，況且Java中int類型表示不下40億個不重復的非負數，需要long類型。總之龐大的數據量導致我們連存儲（以現在的內存）都是問題。

因此，引入了位圖，位圖其實就是哈希的應用，一個位代表一個數字，1表示存在，0表示不存在，存放和查找遵循某種映射關系。此時一個數字的信息從4字節（32位）或是8字節（64位）直接壓縮至1位，同時查找時間復雜度為O(1)。

結合下圖理解：

• 圖中僅展示了3位，但是足以表示數字0~23，上面數組存在的數字都在位圖里體現了

• 實際上位圖本身通常是一個數組，可以是byte類型的，也可以是int類型的等等。

  假設上圖展示的就是一個byte類型的數組，那么[1]存儲的就是0~7數字的信息，后面的同理。此時假設將15插入位圖，代碼方面怎么處理？

  1. 確定數組下標：15 / 8 = 1
  2. 確定在該下標的哪一位：15 % 8 = 7
  3. 設置為1即可

---

【代碼實現】

有關位圖，Java中有現成類BitSet，不過我們這里是要自己實現一個簡單的位圖類，熟悉位圖常用方法和練習位運算。

public class BitSet {public int[] set;// n個數字 : 0~n-1public BitSet(int n) {set = new int[(n + 31) / 32];}/*** 添加一個數字* @param num*/public void add(int num) {set[num / 32] |= 1 << (num % 32);}/*** 移除一個數字* @param num*/public void remove(int num) {set[num / 32] &= ~(1 << (num % 32));}/*** 反轉一個數字，即原來存在變為不存在，不存在變為存在* @param num*/public void reverse(int num) {set[num / 32] ^= 1 << (num % 32);}/*** 判斷某個數字是否存在* @param num* @return*/public boolean contains(int num) {return ((set[num / 32] >> (num % 32)) & 1) == 1;}
}

• 具體實現因人而異，可以選擇byte[]數組，如果追求極致的嚴謹性可以在每個方法前加上一些判斷，比如add方法判斷加入的數字是否超出可表示的范圍（但是如果我們提前知道了數據范圍，準備好足夠的空間即可），也可以加入一些屬性，比如當前存在的有效數字的數量等等。
• 注意，remove方法不能使用異或（set[num / 32] ^= 1 << (num % 32);），反例：當原來的位置上是0，那么異或后就變1，與移除方法邏輯不符
• (n + 31) / 32是一個向上取整，當a和b都是非負數時，想要得到a除b的向上取整的寫法：(a + b - 1) / b
• 另外，使用位圖進行排序：比較簡單，依次遍歷，為1就打印映射出的數字即可。

---

【對數器驗證】

對于實現好的位圖，可以選擇對數器的方式驗證，位圖本質上還是哈希表，因此可以使用哈希表來作為對照，即生成一些隨機數字，分別放入位圖和哈希表中，進行一些添加刪除操作，最后驗證結果即可。

public static void main(String[] args) {//測試范圍0~4999int n = 1000;//測試次數int testTimes = 10_000;BitSet bitSet = new BitSet(n);HashSet<Integer> hashSet = new HashSet<>();Random random = new Random();for(int i = 0; i < testTimes; i++) {int op = random.nextInt(3);int number = random.nextInt(1000);if(op == 0) {bitSet.add(number);hashSet.add(number);}else if(op == 1) {bitSet.remove(number);hashSet.remove(number);}else {bitSet.reverse(number);if(hashSet.contains(number)) {hashSet.remove(number);}else {hashSet.add(number);}}}System.out.println("驗證階段開始！");for(int i = 0; i < n; i++) {if(bitSet.contains(i) != hashSet.contains(i)) {System.out.println("測試出錯！");}}System.out.println("驗證階段結束！");}

• 思路：先規定數字范圍和操作次數，然后進行規定次數的操作，具體操作和數字隨機生成，位圖和哈希表針對隨機數字執行隨機操作，最后驗證容器中元素狀態是否一致，如果出錯則打印出錯。

  多次測試發現，代碼無誤。

---

題目練習

測試鏈接：2166. 設計位集 - 力扣（LeetCode）

---

一道實現位圖的題目，理解了位圖實現后難度不大，只是多了幾個方法和要求，這里給出左程云大佬的實現：

class Bitset {private int[] set;private final int size;private int zeros;private int ones;private boolean reverse;//標識是否翻轉過，false就表示保持原含義，1存在，0不存在；true則相反，1為不存在，0存在public Bitset(int n) {set = new int[(n + 31) / 32];size = n;zeros = n;ones = 0;reverse = false;}// 把i這個數字加入到位圖public void fix(int i) {int index = i / 32;int bit = i % 32;if (!reverse) {// 位圖所有位的狀態，維持原始含義// 0 : 不存在// 1 : 存在if ((set[index] & (1 << bit)) == 0) {zeros--;ones++;set[index] |= (1 << bit);}} else {// 位圖所有位的狀態，翻轉了// 0 : 存在// 1 : 不存在if ((set[index] & (1 << bit)) != 0) {zeros--;ones++;set[index] ^= (1 << bit);}}}// 把i這個數字從位圖中移除public void unfix(int i) {int index = i / 32;int bit = i % 32;if (!reverse) {if ((set[index] & (1 << bit)) != 0) {ones--;zeros++;set[index] ^= (1 << bit);}} else {if ((set[index] & (1 << bit)) == 0) {ones--;zeros++;set[index] |= (1 << bit);}}}public void flip() {reverse = !reverse;int tmp = zeros;zeros = ones;ones = tmp;}public boolean all() {return ones == size;}public boolean one() {return ones > 0;}public int count() {return ones;}public String toString() {StringBuilder builder = new StringBuilder();for (int i = 0, k = 0, number, status; i < size; k++) {number = set[k];for (int j = 0; j < 32 && i < size; j++, i++) {status = (number >> j) & 1;status ^= reverse ? 1 : 0;builder.append(status);}}return builder.toString();}}

• 這種實現的效率是很高的（至少比我寫的高），通過維護一個布爾變量reverse來避免翻轉方法的遍歷。

---

完