在講解位運算之前我們來總結(jié)一下常見的位運算

一、常見的位運算

1.基礎(chǔ)為運算

<<? ? ? &：有0就是0

>>? ? ? |：有1就是1

~? ? ? ? ^：相同為0，相異位1 /無進位相加

---

2.給一個數(shù) n，確定它的二進制表示中的第x 位是0還是1

n：0 1 1 0 1 0 1 0 0 1

(n >> x) & 1

---

3.將一個數(shù)n的二進制表示的第x位修改成1

? ? ? ? ? ? ? ?x

0 1 1 0 1 0 1 0 1 1

0 0 0 0 0 1 0 0 0 0

0 1 1 0 1 1 1 0 1 1(使用|)

n |=(1 << x)

n = n | (1 << x)

---

4.將一個數(shù)n的二進制表示的第x位修改成0

? ? ? ? ? ? x

0 1 1 0 1 0 1 1 0 0

1 1 1 1 0 1 1 1 1 1(取反得到:0 0 0 0 0 1 0 0 0 0)

0 1 1 0 0 0 1 1 0 0(使用&)

n &= (~(1<<x))

n = n &(~(1<<x))

---

5.位圖思想

我們可以使用一個哈希表來存儲我們的信息方便我們增刪查改主要還是為了 我們查找因為可以使用O(1)的時間復雜度來查找，但是現(xiàn)在我們可以使用一個int變量來進行，一個int類型4個字節(jié)32個bit位，我們可以用某一位bit位上的0或者1來表示我們的信息，0表示一個信息1表示一個信息，本質(zhì)還是一個哈希表。

位圖會大量用到我們2、3、4這幾個操作，專門為位圖服務(wù)

---

6.提取一個數(shù)(n)二進制中最右側(cè)的1

n & -n 將最右側(cè)的1，左邊的區(qū)域全部變成相反

0 1 1 0 1 0 1 0 0 0(原碼)

1 0 0 1 0 1 0 1 1 1(反碼)

1 0 0 1 0 1 1 0 0 0(+1,補碼)

0 1 1 0 1 0 1 0 0 0(原碼)

0 0 0 0 0 0 1 0 0 0(原碼和補碼進行&)

---

7.干掉一個數(shù)(n)二進制表示中最右側(cè)的1

n & (n-1)將最右側(cè)的1，右邊的區(qū)域(包含1)全部變成相反

n ：? ?0 1 1 0 1 0 1 0 0

n -1：0 1 1 0 1 0 0 1 1

&? ? ? ? 0 1 1 0 1 0 1 0 0

___________________

? ? ? ? ? ?0 1 1 0 1 0 0 0 0

---

8.位運算的優(yōu)先級

能加括號就加括號

---

9.異或(^)運算的運算律

1.a ^ 0 = a

2.a ^ a = 0(消消樂)

3.a ^ b ^ c = a ^(b ^ c)

一個奇數(shù)，一堆偶數(shù)最終的結(jié)果為奇數(shù)，因為偶數(shù)抵消了為0

---

通過上面的總結(jié)我們可以嘗試寫一下如下五個題

191.位一個的個數(shù)

題目鏈接：位一個的個數(shù)

題目描述：

參考代碼：

class Solution {
public:int hammingWeight(int n) {int count = 0;while(n != 0) {count++;n = n & (n-1);//把最低位1的右邊互為相反數(shù)(包含1)}return count;}
};

---

338.比特位計數(shù)

題目鏈接：比特位計數(shù)

題目描述：

參考代碼：

class Solution {
public:vector<int> countBits(int n) {vector<int>ans(n+1,0);for(int i = 1;i <= n;i++){ans[i] = ans[i>>1] + (i & 1);}return ans;}
};

---

461.漢明距離

題目鏈接：漢明距離

題目描述：

參考代碼：

//對應(yīng)的位置值不相同的個數(shù)。例如，假設(shè)有兩個十進制數(shù)a=93和b=73，
// 如果將這兩個數(shù)用二進制表示的話，有
// a=1011101
// b=1001001，
// 可以看出，二者的從右往左數(shù)的第3位、第5位不同（從1開始數(shù)）
// 因此，a和b的漢明距離是2。
class Solution {
public:int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;while (s){ret += s & 1;s >>= 1;}return ret;}
};

---

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

題目鏈接：只出現(xiàn)一次的數(shù)字

題目描述：

參考代碼：

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(auto n :nums){ret ^= n;}return ret;}
};

---

260.只出現(xiàn)一次的數(shù)字|||

題目鏈接：只出現(xiàn)一次的數(shù)字|||

題目描述：

參考代碼：

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {unsigned int s = 0;for(auto n : nums){s ^= n;}int low = s & -s;//取出最右側(cè)的1int a = 0,b = 0;for(auto n : nums){if((low & n) == low){a ^= n;}else{b ^= n;}}return vector<int>{a,b};}
};

---

二、判斷字符是否唯一

題目鏈接：判斷字符是否唯一

題目描述：

解法一：我們可以使用哈希表

class Solution1 {
public:bool isUnique(string astr) {unordered_set<int>hash;for (auto ch : astr){if (hash.count(ch)) return false;hash.emplace(ch);}return true;}
};

解法二：位圖

我們用0表示沒出現(xiàn)過，1表示出現(xiàn)過

可以利用鴿巢原理來進行優(yōu)化，鴿巢原理已經(jīng)在雙指針那里講過了這里就不過多贅述，一共有26個字母如果字符串的長度超過則肯定有重復字符，如果字符串的長度大于26那么直接返回false

參考代碼：

class Solution {
public:bool isUnique(string astr) {//利用鴿巢原理來做的優(yōu)化if (astr.size() > 26) return false;int bitMap = 0;for (auto ch : astr){int i = ch - 'a';//判斷字符是否已經(jīng)出現(xiàn)過if ((bitMap >> i) & 1 == 1) return false;//把當前字符加入位圖中bitMap |= 1 << i;}return true;}
};

---

三、丟失的數(shù)字

題目鏈接：丟失的數(shù)字

題目描述：

解法一：哈希表

創(chuàng)建一個哈希表然后遍歷數(shù)組，0出現(xiàn)標記一下，1出現(xiàn)標記一下，3出現(xiàn)標記一下....

解法二：高斯求和

(首項 + 尾項) * 項數(shù) / 2這樣就算出了0~5的和然后我們再減去數(shù)組里面所有數(shù)之和這樣就得出來了

參考代碼：

class Solution1 {
public:int missingNumber(vector<int>& nums) {int n = nums.size();int sum = n * (n + 1) / 2;int ret = 0;for (auto n : nums){ret += n;}return sum - ret;}
};

解法三：位運算(異或運算的運算律)

參考代碼：

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

---

四、兩整數(shù)之和

題目鏈接：兩整數(shù)之和

題目描述：

在筆試中我們不講武德直接return a + b;

解法：位運算(異或運算-無進位相加)

13+28=41

a：? ? ? ?0 0 1 1 0 1

b：? ? ? ?0 1 1 1 0 0

——————————

a^b：? ?0 1 0 0 0 1(a)? ?無進位

進位(a & b)<<1? ?0 1 1 0 0 0? ? ? ? ?我們進位是往前進位所以這里我們右移一位

我們繼續(xù)重復如上操作，先無進位相加再進位

a：? ? ? ?????????0 1 0 0 0 1

b：? ? ? ?????????0 1 1 0 0 0?

a^b：? ?????????0 0 1?0 0 1? 無進位

(a & b) <<1? 1 0?0 0 0 0? 進位

?a：? ? ? ? ? ? ? 0 0 1?0 0 1?

?b ：? ? ? ? ? ? ?1 0?0 0 0 0?

a^b：? ? ? ? ? ?1 0 1 0?0 1??無進位? ? 41

(a & b) <<1? ?0 0 0 0 0 0?進位

進位變成0就結(jié)束了，最后的無進位相加就是我們的最終結(jié)果

參考代碼：

class Solution {
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b;//無進位相加unsigned carry = (unsigned)(a & b) <<1;//算出進位a = x;b = carry;}return a;}
};

---

五、只出現(xiàn)一次的數(shù)字||?

題目鏈接：只出現(xiàn)一次的數(shù)字||?

題目描述：

設(shè)要找的數(shù)位 ret ，由于整個數(shù)組中，需要找的元素只出現(xiàn)了?次，其余的數(shù)都出現(xiàn)三次，因此我們可以根據(jù)所有數(shù)的某?個?特位的總和 %3 的結(jié)果，快速定位到 ret 的?個?特位上的值是 0 還是 1 。 這樣，我們通過 ret 的每?個?特位上的值，就可以將 ret 給還原出來。

?參考代碼：

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

---

六、消失的兩個數(shù)字

題目鏈接：消失的兩個數(shù)字

題目描述：

這道題其實是丟失的數(shù)字+只出現(xiàn)一次的數(shù)字|||融合一起，本題的算法原理就是用到了這兩道題的一個算法原理。

nums中消失了兩個數(shù)字，1~N這堆數(shù)中假設(shè)a和b是消失的兩個數(shù)字，nums這一堆數(shù)和1~N這一堆數(shù)異或，其他的數(shù)出現(xiàn)了2次a和b出現(xiàn)了一次，那么其實就是a ^ b

解法：位運算

1.將所有的數(shù)異或在一起，tmp

tmp = a ^ b

2.找到tmp中，比特位上為1的那一位

a^b的結(jié)果肯定不為0因為他們是不同的數(shù)，所以它們的比特位上肯定有一位是1，a和b的第x位上肯定是不同的

3.根據(jù)x位的不同，劃分成兩類異或

我們可以把x位是0的分為一類，x位上是1的分一類，然后對兩組數(shù)據(jù)分別進行異或。

參考代碼：

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//1.把所有數(shù)異或起來int tmp = 0;for(auto n : nums) tmp ^= n;for(int i = 1;i<=nums.size()+2;i++) tmp ^= i;int diff = 0;//找出a,b比特位不同的那一位while(1){if(((tmp >>diff) & 1) == 1) break;else diff++;}//3.根據(jù)diff位的不同，將所有數(shù)劃分兩類來異或int a = 0,b = 0;for(auto n : nums)if(((n >> diff) & 1) == 1) b ^= n;else a ^= n;for(int i = 1;i<=nums.size()+2;i++){if(((i >> diff) & 1) == 1) b ^= i;else a ^= i;}return {a,b};}
};