一、 運算符
- & 與運算： 兩個位都是 1 時，結果才為 1，否則為 0
- | 或運算： 兩個位都是 0 時，結果才為 0，否則為 1
- ^ 異或運算： 兩個位相同則為 0，不同則為 1
- ~ 取反運算：0 則變為 1，1 則變為 0
- << 左移運算：向左進行移位操作，高位丟棄，低位補 0 （每左移一位相當于乘一次2）
- >> 右移運算：向右進行移位操作，對無符號數，高位補 0，對于有符號數，高位補符號位 （每右移一位相當于除一次2）
二、 應用場景
^ 異或運算性質：
（1）交換律
（2）結合律（即(a^b)^c == a^(b^c)）
（3）對于任何數x，都有x^x=0，x^0=x
（4）自反性 A ^ B ^ B = A ^ 0 = A
常見應用：
- 與運算的應用：（1）清零。如果想將一個單元清零，即使其全部二進制位為0，只要與一個各位都為零的數值相與，結果為零。 （2）取一個數中指定位
- 或運算的應用： 對一個數的某幾位補1
- 異或運算的應用： 消去一對重復的數（利用上面）， 交換變量等等。
- 取模： 位運算比加減乘除更加高效。 所以在一些底層的組件例如jdk， redis 中經常用位運算，比如用<< ，>>代替乘除， 用& 代替取模操作。
- 狀態壓縮和位圖： 位運算可以用壓縮存儲和表示信息。 每個二進制位有0|1 兩種狀態， 那一個int32 可以表示出 32種狀態。 比如linux中的文件狀態中的read ，write， 和執行權限就可以用三個二進制位表示， 7（111）表示有Read的權限，有Write的權限和執行的權限。
三、 例題
1、 不使用中間變量交換兩數
// 思路： 利用上面提到的異或的結合率 和自反率
// a = (a ^ b) ^ b , b = a ^ b ^ a
void swap(int &a, int &b) {a ^= b;b ^= a;a ^= b;
}
2、 數組中，只有一個數出現一次，剩下都出現兩次，找出出現一次的數 (leetcode - 136)
public int singleNumber(int[] nums) {int res = 0;for(int i = 0; i < nums.length; i++) {res = res ^ nums[i];}return res;}3、 用 O(1) 時間檢測整數 n 是否是 2 的冪次 （LintCode - 142）
/** 思路： 常用技巧：n&(n-1)消去n 的二進制最后一位的1
* 比如3&(3-1) = (11)&(10) = (10) ,
* 如果是2的冪次， 那二進制形式下只有一位是1， 消去后為0
*/ public boolean checkPowerOf2(int n) {if(n <= 0) return false;return (n & (n - 1)) == 0;}4、子集列舉 （leetcode - 78 medium）
描述：
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]思路：（這道題遞歸做感覺也很容易理解）
注意數組中數字唯一，可以把這道題理解成高中數學中的排列組合問題。每個數字有取或不取兩種可能性， n個數有2的n次方個子集。 可以用一個正整數二進制表示的第i位是1還是0，代表集合的第i個數取或者不取。類似下圖：
0 000 {}
1 001 {1}
2 010 {2}
3 011 {1,2}
4 100 {3}
5 101 {1,3}
6 110 {2,3}
7 111 {1,2,3}A：
vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size()int p = 1 << n;vector<vector<int>> subs(p);for (int i = 0; i < p; i++) {for (int j = 0; j < n; j++) {// 用 i>>j & 1的方式遍歷每一位if ((i >> j) & 1) {subs[i].push_back(nums[j]);}}}return subs;}
5、 位圖
描述：有一千萬個整數，整數范圍在1到1億之間， 如何快速查找某個整數是否在這1千萬個整數中。
思路： 用一個bit 數組來存儲這1-1億之間的數。如果數字存在， 在對應的下標上標1， 1億個數只需要1億個bit位。
public class BitMap { // Java 中 char 類型占 16bit，也即是 2 個字節private char[] bytes;private int nbits;public BitMap(int nbits) {this.nbits = nbits;this.bytes = new char[nbits/16+1];}public void set(int k) {if (k > nbits) return;int byteIndex = k / 16;int bitIndex = k % 16;bytes[byteIndex] |= (1 << bitIndex);}public boolean get(int k) {if (k > nbits) return false;int byteIndex = k / 16;int bitIndex = k % 16;return (bytes[byteIndex] & (1 << bitIndex)) != 0;}
}
)
