在講解位運(yùn)算之前我們來(lái)總結(jié)一下常見(jiàn)的位運(yùn)算

一、常見(jiàn)的位運(yùn)算

1.基礎(chǔ)為運(yùn)算

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

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

~? ? ? ? ^：相同為0，相異位1 /無(wú)進(jìn)位相加

---

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

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

(n >> x) & 1

---

3.將一個(gè)數(shù)n的二進(jì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.將一個(gè)數(shù)n的二進(jì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.位圖思想

我們可以使用一個(gè)哈希表來(lái)存儲(chǔ)我們的信息方便我們?cè)鰟h查改主要還是為了 我們查找因?yàn)榭梢允褂肙(1)的時(shí)間復(fù)雜度來(lái)查找，但是現(xiàn)在我們可以使用一個(gè)int變量來(lái)進(jìn)行，一個(gè)int類(lèi)型4個(gè)字節(jié)32個(gè)bit位，我們可以用某一位bit位上的0或者1來(lái)表示我們的信息，0表示一個(gè)信息1表示一個(gè)信息，本質(zhì)還是一個(gè)哈希表。

位圖會(huì)大量用到我們2、3、4這幾個(gè)操作，專(zhuān)門(mén)為位圖服務(wù)

---

6.提取一個(gè)數(shù)(n)二進(jì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,補(bǔ)碼)

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

0 0 0 0 0 0 1 0 0 0(原碼和補(bǔ)碼進(jìn)行&)

---

7.干掉一個(gè)數(shù)(n)二進(jì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ùn)算的優(yōu)先級(jí)

能加括號(hào)就加括號(hào)

---

9.異或(^)運(yùn)算的運(yùn)算律

1.a ^ 0 = a

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

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

一個(gè)奇數(shù)，一堆偶數(shù)最終的結(jié)果為奇數(shù)，因?yàn)榕紨?shù)抵消了為0

---

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

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

題目鏈接：位一個(gè)的個(gè)數(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.比特位計(jì)數(shù)

題目鏈接：比特位計(jì)數(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.漢明距離

題目鏈接：漢明距離

題目描述：

參考代碼：

//對(duì)應(yīng)的位置值不相同的個(gè)數(shù)。例如，假設(shè)有兩個(gè)十進(jìn)制數(shù)a=93和b=73，
// 如果將這兩個(gè)數(shù)用二進(jìn)制表示的話(huà)，有
// a=1011101
// b=1001001，
// 可以看出，二者的從右往左數(shù)的第3位、第5位不同（從1開(kāi)始數(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表示沒(méi)出現(xiàn)過(guò)，1表示出現(xiàn)過(guò)

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

參考代碼：

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

---

三、丟失的數(shù)字

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

題目描述：

解法一：哈希表

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

解法二：高斯求和

(首項(xiàng) + 尾項(xiàng)) * 項(xiàng)數(shù) / 2這樣就算出了0~5的和然后我們?cè)贉p去數(shù)組里面所有數(shù)之和這樣就得出來(lái)了

參考代碼：

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;}
};

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

參考代碼：

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;

解法：位運(yùn)算(異或運(yùn)算-無(wú)進(jìn)位相加)

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)? ?無(wú)進(jìn)位

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

我們繼續(xù)重復(fù)如上操作，先無(wú)進(jìn)位相加再進(jìn)位

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

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

a^b：? ?????????0 0 1?0 0 1? 無(wú)進(jìn)位

(a & b) <<1? 1 0?0 0 0 0? 進(jìn)位

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

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

a^b：? ? ? ? ? ?1 0 1 0?0 1??無(wú)進(jìn)位? ? 41

(a & b) <<1? ?0 0 0 0 0 0?進(jìn)位

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

參考代碼：

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

---

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

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

題目描述：

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

?參考代碼：

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;}};

---

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

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

題目描述：

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

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

解法：位運(yùn)算

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

tmp = a ^ b

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

a^b的結(jié)果肯定不為0因?yàn)樗麄兪遣煌臄?shù)，所以它們的比特位上肯定有一位是1，a和b的第x位上肯定是不同的

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

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

參考代碼：

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//1.把所有數(shù)異或起來(lái)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ù)劃分兩類(lèi)來(lái)異或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};}
};