# 位元運算 ## 進位制 人類使用進位制以有限數字表達無限大小，常見的進位制有:十進位、二進位、八進位、十六進位等，我們平常使用的就是十進位制(因為人類有十根手指)。 關於進位制的計算方式，會是以當前位數(以0為初始，從右往左數)作為上標，再將每位相加。我以十進位舉例如下: ``` 314 = 3 x 10^2 + 1 x 10^1 + 4 x 10^0 ``` 以同樣的方式我們可以計算其他進位制的大小，我給幾個數字，你可以先試看看: ``` 0b1011 = 11 // ob開頭表示二進位(binary) 0o125 = 85// 0o開頭表示八進位(octal) // 十六進位數以數字0~9和英文字母a(10)~f(15)組成 oxA7 = 167 // 0x開頭表示十六進位(hexadecimal) ``` 在計算機中，我們使用二進位表示一切，包括圖片，原因是二進位最好實現，可以簡單的用1和0分別表示電路通電和不通電(高電壓和低電壓)。 ## 位元運算 計算機中的每一位二進位數稱作**位元(bit)**，而為了方便管理，將每八位元定義為**位元組(byte)**。 位元運算就是將數字逐位元的計算，不常用，但在某些地方會有奇效。 | 位元運算子 | 名稱 | | ----- | -- | | & | AND | | \ | OR | | ^ | XOR | | ~ | 補數 | | << | 左移 | | >> | 右移 | >[!Note]使用位元運算時請注意運算子的優先順序! ### & 和 | | & | a為0 | a為1 | | --- | ---- | ----- | | b為0 | 0 | 0 | | b為1 | 0 | 1 | | \| | a為0 | a為1 | | -- | ---- | ----- | | b為0 | 0 | 1 | | b為1 | 1 | 1 | 可以發現它們的名字和邏輯運算子相同，兩者確實有一定的相似性，但不是同種東西。 因為我們會將數字轉成二進位來看，因此只會有0和1的比較。當進行AND運算時，除非兩者皆為1，否則為0 ; 進行OR運算時，除非兩者皆為0，否則為1。 ```cpp= // << 和 >>的優先級大於&和|，因此需要括號防止邏輯錯誤 cout << (5 & 9) << "\n"; // 5 & 9 => 0101 & 1001 => 1 cout << (7 | 11) << "\n"; // 7 | 11 => 0111 | 1011 => 1111 => 15 ``` output ``` 1 15 ``` 在除數是2的冪次時，&可以代替%進行更有效率的取餘數，像是判斷某數是否為偶數時一般是寫```a % 2 == 0```，但可以用AND寫成```(a & 1) == 0```。 ```cpp= int num = 5; if ((num & 1) == 0) // 0101 & 0001 -> 0001 = 1 cout << num << "是偶數" << "\n"; else cout << num << "是奇數" << "\n"; ``` output ``` 5是奇數 ``` ### ^ XOR有一種很特殊的轉換方式，因此常用於訊息加密，規則如下 | ^ | a為0 | a為1 | | --- | ---- | ----- | | b為0 | 0 | 1 | | b為1 | 1 | 0 | 你可以理解為 : 當兩數相異且不為零時等於1，否則為0。 從這規則可以推導出XOR的3大特性 : 1. 相同數字經過 XOR 後會等於0 ``` a ^ a => 0 ``` 2. 任何數和0 XOR 後會等於自己 ``` a ^ 0 => a ``` 3. XOR運算具有交換律 ``` a ^ 0 => 0 ^ a ``` ---- 根據上述特性，我們主要可對XOR進行兩種應用 #### 1. 進階兩數交換 當我們想將兩個變數內的值進行互換時，最直覺的方法是使用第三個變數儲存，這在之前就說明過了，雖然簡單，但有一個缺點，為了暫存值我們被迫創建了一個不怎麼會使用的變數，從而消耗了更多的記憶體，而這是可避免的，方法是使用XOR來代替。 ```cpp= int a = 3, b = 5; a ^= b; // a = 011(a) ^ 101(b) => 0110 => 6 , b = 5 b ^= a; // b = 101(b) ^ 110(a) => 0011 => 3 , a = 6 a ^= b; // a = 110(a) ^ 011(b) => 0101 => 5 , b = 3 cout << "a = " << a << "\n"; cout << "b = " << b << "\n"; ``` 如果要追求簡潔，你甚至可以寫成 ```cpp= int a = 3, b = 5; a ^= b ^= a ^= b; cout << "a = " << a << "\n"; cout << "b = " << b << "\n"; ``` output ``` a = 5 b = 3 ``` 上述程式有一個小bug，就是當a和b相等時，使用XOR交換會導致兩者的值皆變為零，因此請加上一個a和b不相等的判斷: ```cpp= void swap(int &a, int &b) { if (a != b) { a ^= b ^= a ^= b; // 這樣就完美啦! } } ``` #### 2. Single Number 這是一種**演算法**問題，有很多種解法，而使用XOR是最優解的其中之一。 問題描述 : 給定一個由整數組成的列表，陣列中大部分的數皆兩兩成對，唯有一個例外，請找出該陣列中只出現過一次的數值。 ``` example : [1, 2, 2, 4, 3, 1, 3] => single number = 4 ``` 想想看剛才提到的XOR三大特性，該怎麼運用他們解決 ? <details> <summary>Answer Code</summary> ```cpp= int nums = {1, 2, 2, 4, 3, 1, 3}; int singleNum = 0; for (const int& num : nums) singleNum ^= num; cout << singleNum << "\n"; ``` </details> 讓我們看看為什麼可以這樣寫 : 首先，根據XOR的交換律，```[1, 2, 2, 4, 3, 1, 3] => [1, 1, 2, 2, 3, 3, 4]``` ; 再來，把這些數字都進行XOR，根據**相同數經過XOR會得到0**和**任何數經過XOR都會得到自己**的特性，可以寫成下列樣式 ``` 1 ^ 1 => 0 2 ^ 2 => 0 3 ^ 3 => 0 0 ^ 4 => 4 ``` 因此，我們成功的找出了single number。 題目連結 - [136. Single Number](https://leetcode.com/problems/single-number/description/) ##### AC Code (0ms, 20.81MB) <details> <summary>Code</summary> ```cpp= class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; for(const int &num : nums){ ans ^= num; } return ans; } }; ``` </details> ### >> 和 << 就只是乘除2的冪次而已，稍快於*和/ ```cpp= int num = 10; cout << num << " << 2 = " << (num << 2) << "\n"; // 10 => 01010 => 00010 => 2 cout << num << " >> 2 = " << (num >> 2) << "\n"; // 10 => 0001010 => 0101000 => 4 ``` output ``` 10 << 2 = 40 10 >> 2 = 2 ``` 將數字轉成二進位來看更明顯，左移是將每位元往左移動，跑出去的零丟到後面，也就是乘2 ; 右移則是將每位元往右移動，比較特別，整除時是除以2，但不整除時會有一種叫位元遮罩的東西，不管是0 和 1都會捨棄。 ## ~ 補數運算的規則很簡單，0變成1 ; 1變成0。 | 補數 | a為0 | a為1 | | --- | ---- | ----- | | 結果 | 1 | 0 | 值得一提的是，它負責處理電腦二進位的減法邏輯，是負數的轉換方法，稱為「**二補數**」。 以int型態的11舉例，其二進位為 ``` 00000000 00000000 00000000 00001011 ``` 而-11的二進位數字就是將11進行補數運算後的結果 ``` 11111111 11111111 11111111 11110100 ``` ## 總結 計算機以二進位表示一切，而二進位數字間有獨特的運算方式，稱作**位元運算**。 位元運算共有六種，分別為```&、|、^、~、<<、>>```，其中```&```用來進行二冪次的取餘數，```^```用來進行兩數交換，```~```可以轉換二進位制下的負數，```|```則是幾乎不會使用到。