關于運算子/位操作 的操作方法和應用 附加（整形提升）（C語言)

關于運算子/位操作 的操作方法和應用 附加（整形提升）（C語言)

1.了解什么是位操作（二進制數，位）
2.關于位運算子的詳解（ ‘&’ ‘|’ ‘~’ )
3.位移運算子(">>","<<")
4.位異或的一些妙用

Hellolo
關于這一章的話，之所以想成寫一篇博客是因為這一章在我們學校高級語言程式課中基本就是草草概括，正巧寒假開始資料結構，也在Leetcode上了解到可以巧妙運用位操作來解決一些時間空間”雙殺“的問題，
所以，一鼓作氣，寫下這篇Blog，也好讓自己鞏固這一方面知識，

1.位操作
相信大家對于運算子都不陌生，每個語言都有著自己的運算子，在C語言中，運算子分為：
算術、位移、位、賦值、單目、三目（條件）、關系、邏輯、逗號 運算子
而本篇blog主要介紹位運算子：
要想知道位運算子，首先得知道什么是”位“
了解“位”之前，我覺得很有必要了解一下“二進制位計演算法”
進制
很多時候，身邊沒有計算機的情況下，如果我們要轉換進制數，其實是一件非常簡單的一件事，舉個栗子，我們生活中最常使用的十進制數字：1729 來說
我們可以這樣轉化：每個數字都有著各自的權重 ，9是個位，2是十位，7是百位，1是千位，所以 1729 = 11000 + 7100 + 210 + 91
當然這種方法我個人不喜歡，不如換一個方法，這個方法專業叫法是”以N為基底書寫XXX“(這里的N為進制數，XXX為你要轉化的數字)
就拿剛剛的例子，就為，”以10為基底書寫1729“
那么好了，這樣就是：1729 = 1 * 10^3 + 1 * 10^2 + 1 * 10^1 + 1*10^0

這是我們的10進制
但是機器可就沒我們這么厲害了，它只識得1和0 （關倍訓者打開）
這也就導致我們經常在編程程序中運用最多的是二進制

但是了解了剛剛的”基底書寫“，二進制的轉化也很簡單不是嗎？
eg:將二進制101轉化成十進制？
那么就是 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5

現在我們都知道了，機器相對于聰明的人類來講，思考和計算還是比較吃力的，但身為一個程式員，我們必須要掌握如何利用二進制系統來表示1位元組和整數，

比如，在現實生活中我出去買零食，10元的奶茶+5元的薯片 讓我剛剛踏入幼兒園的表弟來算都知道 10 + 5 = 15 需要15元
而計算機則不然，它是這樣算的*(這里為了好理解，用C語言來解釋）*：

int a = 10;
int b = 5;
int c = a + b;
//最終需要c，這么多的錢 

當然了，如果真是眼看著這樣的話，那我剛剛說的都白說了
實際上:

int a = 10;
//10 -轉化為二進制
//00000000000000000000000000001010 - 10
int b = 5;
//5 - 轉化為二進制
//00000000000000000000000000000101 - 5
int c = a + b;
//00000000000000000000000000001010
//00000000000000000000000000000101
//上述兩式子相加后得到
//00000000000000000000000000001111 - 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0 = 15

這就是計算機運用的二進制計算的原理

這就引出了以下”三匹馬”（個人覺得有意思就這么想出了這種記法~）
原碼、補碼、反碼
上述代碼中
將10轉化為二進制后得到的就是該數字的*“原碼”*
即00000000000000000000000000001010 - 10的原碼
而存于計算機記憶體中的卻不是原碼
而是補碼，補碼很重要！因為存在計算機記憶體中，所以計算和處理的時候，都是補碼在作業！
補碼怎么得到呢？（這里拿int整數來舉例子)
這里要看這個數字的正負了（這里由于太深奧，總的來說，有符號的整數取決于硬體，和各種語言沒任何關系，具體嘛，，我也不知道~~~QAQ）
這里引出一個叫做 符號量(sign - magnitude) 的表示法 即正數符號位為0,負數符號位為1，
在這基礎上：
1.正整數 —> 原碼反碼補碼統統相同
2.負整數 —> 原碼反碼補碼需要通過計算得到 （原碼–>反碼–>補碼)

這里就不繼續解釋這“三匹馬”了，停！
讓我們趕緊回到剛剛的代碼中，現在我們曉得了，正整數的原反補都是一樣的，那么就好辦了，把補碼兩者相加，得到的即就是c的補碼–>原碼
00000000000000000000000000001010 ----10的補碼
00000000000000000000000000000101 ---- 5的補碼

=
00000000000000000000000000001111 — 15的補碼 也即原碼

這樣大家就都明白了吧~~
但是這個時候就有人問了，我需要知道這玩意干啥！？
emmm說實話一開始我也覺得知道這玩意好像沒啥用，但是你看看下面的代碼，看看你能不能一下子算出結果~

char a = 3;
char b = 127;
char c = a + b;
printf("%d ",c);
//C為多少?

哦！對！還要再講一個東西！不然這題解不了，
叫做————整型提升

運算式的整形原型要在CPU的相應運算期間內執行，CPU內整形運算器（ALU）的運算元的位元組長度一般就是int的位元組長度，同時也是CPU的通用暫存器長度，
因此，即使兩個char型別相加，在CPU執行時，也要先轉換成int型別才能計算

好了，我說完了，我也把答案放出來吧

不能理解很正常，我把程序再放出來你就理解了~

這里有個要注意的地方，整形提升是將符號位補齊哦！

好了，終于我們終于了解二進制運算了！
那我們可以用二進制計數法來了解位的操作了

##位操作

首先先宣告一下，本Blog用的是8位二進制數，也即一個位元組（Byte）
除了第一位我們剛剛介紹的符號位*（sign - magnitude) 外，其他0~7位，我們稱為“位” 從左到右，編號為 7 ~ 0 其中7為最高位，0為最低位，*

還有要注意的是，運算程序中，統統為補碼在作業哦，前面提到過了，

1. 按位與運算子‘ &’
   不光是C語言，“與”我們已經很熟悉了，運算式中，只要有一方為假（0），即整個式子就為假（0），只有當兩方為真（1），最后回傳值才為真（1）
   舉個例子:
   你和你女朋友出去約會：你問她想去哪？
   她說：“海邊和圖書館”
   懂我意思嗎？那肯定兩個地方都要去！

eg: (00010010) & (10011110) = 00010010
(10010011) & (00111101) = 00010001

還可以順帶掌握 “&=”
a &= 0001 等價于 a = a & 0001

2. 按位或 ’ |’
   運算式中，只要一方為真(1)，即為真(1)

   和上面的例子一樣
   但是這次她說：海邊或圖書館吧
   那你選擇一個你覺得更浪漫的地方去就好了~

eg:(00010010) | (10011110) = 10011110
(10010011) | (00111101) = 10111111
相同的，也有 “|=”
用法和上面"&="一樣

3. 按位異或 ’ ^’
   運算式中，相異為真（1），相同為假（0）
   這個，，不太好舉物體例子，但是！聰明的你看完下面的代碼肯定也很好理解的！
   eg:(10010011) ^ (00111101) = 10101110

   還有一個 “^=”，用法見上，

4.按位取反 ’ ~‘
把補碼中1變成0,0變成1就好了
eg:~(10011010) = (01100101)

##位移運算子

*同樣的，這里也使用二進制數

1.左移 " << "
規則：整體向左移動N位（拋棄），然后右邊補0
假設 a = 1
現在 int b = a<<1
未移動前：

移動后:

eg : int b = 5 << 1
b = 10
所以，左移其實有乘以2^n的效果

2 右移 “>>”

規則：1.算術右移（ 左邊用原來的數字補齊，右邊丟棄）
2.邏輯右移 （左邊用0補齊，右邊丟棄）

這里要說明一下，現在大部分編譯器支持的都是算術右移，所以我們這里只講算術右移，邏輯右移如果有興趣可以下去自己試試，兩者有時結果不一樣

未移動前：

移動后：

eg: int b = 8 >> 1 = 4
所以和左移相反，右移有著除以2^n的效果

##按位異或的一些妙用

呼，終于寫到了這，
其實到了這才真正開始燒腦

首先，按位與是一個很有意思的運算方式，
首先先介紹一下按位異或的兩個小特點：
1.0與N異或 = N
即 0 ^ 2 = 2; 0 ^ 4 = 4;
2.N與N異或 = 0
即 1 ^ 1 =0; 2 ^ 2 = 0;
知道了這兩點之后，再來看接下來的內容

這是一道Leetcode上的題目
博主開始遇到這題第一想法是排序后與0~n的的陣列進行比較，然后找出漏掉的那個數
但是！這里有限制，那就沒法排序了啊，要知道博主若使用快速排序(時間復雜度為(O(n*log(n))都不行，更何況冒泡排序（時間復雜度為O(N^2))
所以，學到了一招騷方法

用異或來寫
思路：設定一個num = 0；
用num 去和 缺少數的陣列A進行異或，再和陣列B [0,N]去異或
答案就是最后異或出來的數字
原理:相同的兩個數字異或為0,而缺少的數字n在陣列B中存在，所以最后得出結果，

這樣雖說還是遍歷了一遍，但是滿足了題目要求~

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

當然還有很多類似的題目，我覺得凡是需要在陣列中找尋某個數字，和別的陣列比較的那種
都可以用異或這一特點來破解，

The end
2021/1/29 *文章中摘取了《C premier Plus》
leetcode 作者 snowmonster的代碼.