前言

上一篇博客，我們已經把位運算的基礎知識，以及基本運算都掌握啦
上次的習題還是讓人意猶未盡，今天我們來嘗試一下難一點的題目
位運算熟練起來真的讓人覺得做題是一種享受
fellow me

丟失的數字

丟失的數字

思路：
少了一個數字，給他找回來不就好了嗎
讓我想到直接對數組 按位異或 一遍， 然后再對 0-n 按位異或一遍，出現兩次的都消消樂
剩下的就是我們要找的數字

class Solution 
{
public:int missingNumber(vector<int>& nums) {int ans = 0;for(auto x : nums){ans ^= x;   //  按位異或當前數組}for(int i = 0; i <= nums.size(); i++){ans ^= i;    //  重新按位異或一遍  0-n}return ans;}
};

兩整數之和

兩整數之和

思路：
乍一看，不讓我用運算方法，那不是完蛋了嗎
但仔細想想，這不是學了位運算，前面了解到按位異或（^）是無進制加法，按位與（&）是進位
其實可以組合起來使用，我們先算出無進位相加的結果，然后再找出進位，給他加上，再如此反復循環，直到沒有進位

class Solution 
{
public:int getSum(int a, int b) {while(b != 0){int x = a ^ b;    //  無進位相加//  這里無符號  是防止溢出  unsigned int cur = (unsigned int) (a & b) << 1;  // 找出進位a = x;b = cur;}return a;}
};

就這么幾行，想明白了，還是很簡單的

只出現一次的數字II

只出現一次的數字II

思路：
一眼hash直接秒了，但是題目要求常數級空間。。。。。
設要找的數位 ret
由于整個數組中，需要找的元素只出現了「一次」，其余的數都出現的「三次」，因此我們可以根據所有數的「某一個比特位」的總和 %3 的結果，快速定位到 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(auto x : nums){if(((x >> i) & 1) == 1)   //  判斷當前比特位{sum++;    // 累積個數}}sum %= 3;if(sum == 1)   //  符合條件就把ret當前的比特位置為 1{ret = ret | 1 << i;}}return ret;}
};

做完發現位運算真好奇妙

消失的兩個數字

消失的兩個數字

最后一題hard難度結尾吧
思路：
缺了兩個數字，想到前面熱乎的缺一個數字，我們可以按位異或兩遍給他找出來，但是找出來的是兩個數字的異或
所以我們還要處理這兩個數字的異或，分解他們，又想到我們上一次做過的（兩個只出現一次的數字）
好像就是兩個題目的融合，才讓他到了hard的難度

class Solution 
{
public:vector<int> missingTwo(vector<int>& nums) {int ans = 0;for(auto x : nums)ans ^= x;for(int i = 1; i <= nums.size() + 2; i++)ans ^= i;//  現在找到了兩個數字的異或int x = 0, y = 0;ans = ans & (-(long long)ans);  //  提起ans二進制最右側的  1for(auto i : nums) //  分組異或 {   if((i & ans) == ans)x ^= i;elsey ^= i;}for(int i = 1; i <= nums.size() + 2; i++)//  分組異或{if((i & ans) == ans)x ^= i;elsey ^= i;}return {x, y};}
};

prefect 位運算完美收官

總結

今天通過幾道位運算題目，鞏固了位運算的應用技巧：

1. 丟失的數字
   利用異或性質，兩次異或數組和0~n的數，出現兩次的抵消，剩下的即為缺失數。
2. 兩整數之和
   通過異或（無進位加法）和與運算左移（進位）模擬加法，循環處理進位直至為零，注意用unsigned避免溢出。
3. 只出現一次的數字II
   統計每一位1的個數，模3后確定目標數各位的值，逐位組合得到結果。
4. 消失的兩個數字
   結合異或和分組思想，先找到兩數異或結果，提取最右1進行分組，分別異或數組和完整序列得到兩數。
   心得
   位運算題目需靈活運用位操作性質，如異或消重、與運算找進位、按位統計等
   通過分解問題、逐步處理，能將復雜問題簡化，然后逐個擊破

今天的內容就到這里啦，不要走開，小編持續更新中~~~~