---

一、算法原理

計(jì)算機(jī)中的數(shù)據(jù)都以二進(jìn)制形式存儲(chǔ)和處理，位運(yùn)算直接對(duì)二進(jìn)制位進(jìn)行操作。常見的位運(yùn)算符包括與（&）、或（|）、異或（^）、取反（~）和左移（<<）、右移（>>）等。

---

常見的位運(yùn)算總結(jié)

1. 基礎(chǔ)位運(yùn)算
   
2. 給一個(gè)數(shù)n，確定它的二進(jìn)制表示中第x位是0還是1
   
3. 將一個(gè)數(shù)n的二進(jìn)制表示的第x位修改成1
   
4. 將一個(gè)數(shù)n的二進(jìn)制表示的第x位修改成0
   
5. 位圖的思想
   
6. 提取一個(gè)數(shù)(n)二進(jìn)制表示中最右側(cè)的1
   
7. 干掉一個(gè)數(shù)(n)二進(jìn)制表示中最右側(cè)的1
   
8. 位運(yùn)算的優(yōu)先級(jí)： 能加括號(hào)就加括號(hào)
9. 異或(^)運(yùn)算的運(yùn)算律
   

---

二、算法實(shí)戰(zhàn)

1. leetcode面試題01.01. 判斷字符是否唯一

判斷字符是否唯一

解題思路：位圖的思想

這道題目我們可以使用位圖的思想來解決，因?yàn)轭}目告訴我們字符串中只有小寫字母，所以我們只需要一個(gè)int類型的整數(shù)來充當(dāng)位圖的32個(gè)bit位即可。

首先，將位圖的所有bit位置為零，默認(rèn)字符串中的字符都未在位圖中出現(xiàn)過。然后遍歷整個(gè)字符串，檢測(cè)該字符是否在位圖中出現(xiàn)過，如果當(dāng)前字符未在位圖中出現(xiàn)過，說明當(dāng)前字符是第一次出現(xiàn)，此時(shí)我們將其在位圖中的位置（當(dāng)前字符-'a'）置為1即可，然后接著向后遍歷字符串，如果該字符再次出現(xiàn)，我們就可以從位圖中檢測(cè)到該字符已經(jīng)在出現(xiàn)過了。直接返回false即可，否則繼續(xù)向后遍歷字符串，如果遍歷所有字符后發(fā)現(xiàn)都只出現(xiàn)一次，則說明該字符串符合題意。

代碼實(shí)現(xiàn)：

class Solution {
public:bool isUnique(string astr) {int num = 0;for(int i = 0; i < astr.size(); i++){int index = astr[i] - 'a';if(((num>>index) & 1) == 1)return false;elsenum |= 1 << index;}return true;}
};

---

2. leetcode268 丟失的數(shù)字

丟失的數(shù)字

解題思路：異或運(yùn)算

因?yàn)轭}目中告訴我們數(shù)組中【1~n】丟失了一個(gè)數(shù)字，所以我們可以先將數(shù)組中的數(shù)字 ^ 起來，然后在將這個(gè) ^ 的結(jié)果與【1~n】中所有的數(shù)字異或，因?yàn)榘次?^ 運(yùn)算滿足交換律和結(jié)合律，所以按位 ^ 的結(jié)果中，丟失的數(shù)字出現(xiàn)了一次，其余的數(shù)字都出現(xiàn)了兩次，將這一堆數(shù)字異或起來，結(jié)果即為丟失的數(shù)字。

代碼實(shí)現(xiàn)：

class Solution {
public:int missingNumber(vector<int>& nums) {int ret = 0;for(auto e : nums)ret ^= e;for(int i = 1; i <= nums.size(); i++)ret ^= i;return ret;}
};

---

3. leetcode371 兩整數(shù)之和

兩整數(shù)之和

解題思路：異或運(yùn)算-無進(jìn)位相加

因?yàn)轭}目要求我們不能使用運(yùn)算符+和-來計(jì)算兩整數(shù)之和，因此我們可以將整數(shù) a 和 b 的和，拆分為 a 和 b 的無進(jìn)位相加結(jié)果與進(jìn)位結(jié)果的和，無進(jìn)位相加結(jié)果 我們可以使用兩整數(shù)^來實(shí)現(xiàn)，進(jìn)位結(jié)果我們可以使用(a & b) << 1來實(shí)現(xiàn)。下面我們來舉一個(gè)例子：

每次將無進(jìn)位相加結(jié)果與進(jìn)位結(jié)果的和分別賦予a和b，循環(huán)此過程，直到進(jìn)位為 0。最終a就是我們所要求的結(jié)果。當(dāng)我們賦給無符號(hào)類型一個(gè)超出它表示范圍的值時(shí)，結(jié)果是初始值對(duì)無符號(hào)類型表示數(shù)值總數(shù)取模的余數(shù)。因此，我們可以使用無符號(hào)類型來防止溢出。

代碼實(shí)現(xiàn)：

lass Solution {
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b; // 先算出無進(jìn)位相加的結(jié)果unsigned int carry = (a & b) << 1; // 算出進(jìn)位a = x;b = carry;}return a;}
};

---

4. leetcode004 只出現(xiàn)一次的數(shù)字II

只出現(xiàn)一次的數(shù)字II

解題思路：

數(shù)組中的每個(gè)元素的每一個(gè)二進(jìn)制位不是1就是0，而題目中又告訴我們只有一個(gè)元素出現(xiàn)一次，其余元素都出現(xiàn)了三次，所以對(duì)于數(shù)組中的每一個(gè)元素 x，我們使用位運(yùn)算 (x >> i) & 1 得到 x 的第 i 個(gè)二進(jìn)制位，并將它們相加再對(duì) 3 取余，得到的結(jié)果一定為 0 或 1，即為答案的第 i 個(gè)二進(jìn)制位。

所以，答案的第 i 個(gè)二進(jìn)制位就是數(shù)組中所有元素的第 i 個(gè)二進(jìn)制位之和除以 3 的余數(shù)。可以先初始化一個(gè)ret = 0，然后根據(jù)余數(shù)的值來判斷該數(shù)對(duì)應(yīng)的二進(jìn)制位應(yīng)該置為0還是1，如果余數(shù)為1，我們則需要手動(dòng)將該位置置為1，ret |= (1 << i)，否則則不需要處理。

代碼實(shí)現(xiàn)：

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i < 32; i++){int cnt = 0;for(auto e : nums)cnt += ((e>>i)&1);if(cnt % 3)ret |= (1 << i);}return ret;}
};

---

5. leetcode面試題17.19. 消失的兩個(gè)數(shù)字

消失的兩個(gè)數(shù)字

解題思路：

這道題目其實(shí)我們可以用力扣的第260題 只出現(xiàn)一次的數(shù)字III 的思想來做，具體解決方式如下：

因?yàn)閿?shù)組中包含從 1 到 N 所有的整數(shù)，但其中缺了兩個(gè)數(shù)字，現(xiàn)在數(shù)組的長(zhǎng)度為n。所以數(shù)組中原本應(yīng)該包含的數(shù)字是【1，n + 2】。我們可以將原來數(shù)組中的數(shù)字和【1，n + 2】，組合到一起，現(xiàn)在我們就可以將問題轉(zhuǎn)化一下：求數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字。

解決這個(gè)問題我們可以分為兩步：整體異或和分組異或。整體異或：將題目給出的數(shù)組中的所有數(shù)字和【1，n + 2】中所包含的數(shù)字全部異或起來，得到的結(jié)果就是只出現(xiàn)一次的兩個(gè)數(shù)字的異或結(jié)果：a^b。接下來我們需要提取出該數(shù)字二進(jìn)制表示中最低位的1。假設(shè)該位置為第k位，我們就可以把 所有數(shù)中的元素（題目中給出的數(shù)字和【1，n + 2】的數(shù)字）分成兩類，其中一類包含所有二進(jìn)制表示的第 k 位為 0 的數(shù)，另一類包含所有二進(jìn)制表示的第 k 位為 1 的數(shù)。

• 對(duì)于任意一個(gè)在 所有元素中 出現(xiàn)兩次的元素，該元素的兩次出現(xiàn)會(huì)被包含在同一類中；
• 對(duì)于任意一個(gè)在所有元素中只出現(xiàn)了一次的元素，即 x1 和 x2， 他們會(huì)被包含在不同的類中。

因此，我們將這兩類元素分別異或起來，就可以得到不同的兩個(gè)結(jié)果，一個(gè)結(jié)果是x1，另一個(gè)結(jié)果是x2，這兩個(gè)數(shù)字則是只出現(xiàn)一次的兩個(gè)數(shù)字，即本題中我們需要尋找的兩個(gè)消失的數(shù)字。

代碼實(shí)現(xiàn)：

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {int ret = 0;for(int i = 1; i <= nums.size()+2; i++)ret ^= i;for(auto e : nums) ret ^= e;int lowbit = ret & -ret; // 找出最后一個(gè)不同的比特位int ret1 = 0, ret2 = 0;for(int i = 1; i <= nums.size()+2; i++){ // 分組異或if(lowbit & i) ret1 ^= i;else ret2 ^= i;}for(auto e : nums){if(lowbit & e) ret1 ^= e;else ret2 ^= e;}return {ret1, ret2};}
};

---

三、總結(jié)

位運(yùn)算可以直接操控?cái)?shù)字的二進(jìn)制位，節(jié)約內(nèi)存，使程序運(yùn)行更快，可靠性高。在算法中使用位運(yùn)算可以大大降低算法的時(shí)間復(fù)雜度和空間復(fù)雜度，恰當(dāng)?shù)奈贿\(yùn)算使用也能使程序變得更加簡(jiǎn)潔和優(yōu)美。