<style> .reveal .slides { text-align: left; font-size:30px; } </style> # 位元運算 & 快速冪 #### Bitwise Operation & Binary Exponentiation 10/13 preTrain --- ## 位元運算 ### Bitwise Operation ---- 電腦儲存數字都是用一堆 $0$ 和 $1$ (位元) 因此也理所當然可以對「位元」做運算 ---- 複習離散數學中「邏輯」那章學過的邏輯運算真值表 |$P$|$Q$|$P\lor Q$|$P\land Q$|$\neg P$|| |----|----|----|----|----|----| |0|0|0|0|1| |0|1|1|0|1| |1|0|1|0|0| |1|1|1|1|0| ---- 「位元運算」也繼承了這些運算，只是多了**XOR運算** $\oplus$ ```cpp AND運算： OR運算： 0 & 0 => 0 0 | 0 => 0 0 & 1 => 0 0 | 1 => 1 1 & 0 => 0 1 | 0 => 1 1 & 1 => 1 1 | 1 => 1 XOR運算(⊕)： NOT運算： 0 ^ 0 => 0 !0 => 1 0 ^ 1 => 1 1 ^ 0 => 1 !1 => 0 1 ^ 1 => 0 ``` 但是跟「邏輯運算」不同的是，位元運算是一整個位元陣列的運算， 而非單一元素的運算 ---- ## Ex: - $1001\text{ & }0111=0001$ - $1001\text{ | }0111=1111$ - $1001\text{ ^ }0111=1110$ ---- ### XOR 運算 因為 XOR 太多常用性質，所以特別拿出來講 先來幾個基本原則（bitwise xor 的符號一樣用 $\oplus$）： 1. $A \oplus B = B \oplus A$、$(A \oplus B) \oplus C = A \oplus (B \oplus C)$， 也就是有交換律和結合律 2. $A \oplus A = 0$ 3. 若 $A \oplus B = C$，則 $A \oplus C = B$ 4. $A \oplus 0 = A$ 奇妙的[延伸閱讀](https://sam571128.codes/2022/03/29/XOR-Basis/)(建議讀完線性代數再來看) <!-- .element: class="fragment" data-fragment-index="1" --> ---- ### 左移/右移運算 C/C++ 程式裡使用 "<<" 與 ">>" 來表示，表示為位元左移(右移)一格 左移時最左邊會補上 0 而右移時最右邊位元會被移除 ```= 9=1001, 9<<1 = 10010 = 18 (乘 2) 15=1111, 15>>1 = 111 = 7 (除 2 取 floor) 常見用法 (x>>1) 快速除 2, 以及 (x<<1) 和 (x<<1)|1 左子節點和右子節點 ``` ---- ### 補數運算 C/C++ 程式裡使用 "~" 來表示，補數運算為逐位元取反 顛倒一個變數的每個位元的 0 和 1 ```= ~0 = -1, ~1 = -2 常見用法(位元優化 dp 總有一天會遇到) 15 & ~(1 << 1) = 13 // 將第 2 個 bit 設為 0 8 | (1 << 2) = 12 // 將第 3 個 bit 設為 1 ``` ---- ### 位元性質 `if (status)` `while (status)` `for ( ; status ; )` 以上的 `status` 都是非 0 就是 true，也就是裡面都是布林值 所以可以常常看到這種寫法 ---- ```cpp= if(array[x]){ // 若 array[x] 的值非零即會進入 "True" cout << "True"; } else{ // 只有再 array[x] == 0 的時候才會進入這邊 cout << "False"; } while(x){ // 當 x 不是 0 的時候就不會跳出迴圈 x--; cout << x << endl; } ``` ---- 規律性質 例題: [[CPE例題](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/12208.pdf)] 詢問 $x$~$y$ 中所有的數字轉換成二進制後有幾個 $1$ ? 當你把位元攤開來之後 0 : 0 0 0 0 1 : 0 0 0 1 2 : 0 0 1 0 3 : 0 0 1 1 4 : 0 1 0 0 5 : 0 1 0 1 6 : 0 1 1 0 7 : 0 1 1 1 8 : 1 0 0 0 ||每個bit拆開來即可發現規律|| ---- ## 應用 : lowbit(x) 最低的 '1' 位元 ```cpp= x & -x ``` - 根據二的補數，-x 為 ~x + 1 - x 中最低位的位元 1 經過 not 運算後，將在 ~x 中變為最低位的 '0' - 因此對 ~x 加上 1 後，最低位的位元 0 重新變為位元 1 (進位) 且其後的位元都將被設定為 0 - 在 x & -x 後，相同的位元僅剩下最低位的 '1' ---- ## 應用 : 檢查冪次 是否為二的冪次 ```cpp= (x & -x) == x ``` 由於若你為二的冪次，則該數字只會有一個位元(也是最高位元) ---- ## 實作例題講解 ### 練習 1 --- XOR 練習 ```cpp= x = 1919, y = 810 x ^= y ^= x ^= y ``` 請問 x, y 各為多少? ---- 拆開來看即為 ```cpp= x = x ^ y; y = y ^ x; x = x ^ y; ``` 答案為 x 為 $810$, y 為 $1919$ (相等於 swap ( x , y )) but why? <!-- .element: class="fragment" data-fragment-index="1" --> ---- 回想一下 XOR 真值表 ``` XOR運算(⊕)： 0 ^ 0 => 0 0 ^ 1 => 1 1 ^ 0 => 1 1 ^ 1 => 0 ``` 會發現 : 兩個位元不同，就會回傳 $1$ 所以若令 $z=x\oplus y$，則 $z$ 儲存的就會是「$x$ 與 $y$ 不同的位元」 相同的位存 $0$，不同則存 $1$ 之後我們再計算 $x \oplus z, y \oplus z$，分別會變成 $y, x$ ---- ### 練習 2 --- 優先級的練習 會輸出多少? ```cpp= cout << (15 >> 1 + 2); ``` ---- ```cpp= cout<< ( 15 >> 1 + 2 ); ``` ans : $1$ 大多數的位元運算子的運算優先級都比較低， 因此此題的計算過程為 $1 + 2 = 3$, $15=(1111)_{2}$ >> $3 = 1$. 所以不確定優先級的時候最好都要加括號 ---- ### 練習 3 --- 常用的技巧 以下這些能幹嘛? ```cpp= if(x & 1) return 1; else return 0; ``` or ```cpp= return (x & 1); ``` ---- ```cpp= if(x & 1) return 1; // (奇數) else return 0; // (偶數) ``` 判斷 $x$ 的奇偶性 也是常見用法 (比較快) 原因: 由於一個數字的位元組成都是 $2$ 的冪次方 因此 $2^n$ 只有在 $n==0$ 的時候會影響到數字的奇偶性 故只需要判斷最後一個位元 ---- ## bitset - 之前在 STL 中講過，但嚴格上來說他不算 STL - 由於這容器支援位元運算，所以我們還是會用到它 - bitset 算是一種優化過的位元運算容器 - 當我們需要開超過 64 位元時，可以考慮 bitset ---- ### 使用範例 ```cpp= #include<bitset> // bitset #include<iostream> bitset<10> a = 7; bitset<10> b(10); bitset<10> c("10010"); int main(){ b = 5; // 101 b >>= 1; // 10 cout << b << endl; cout << (a | c) << " " << (a & c) << " " << (a ^ c) << endl; } ``` --- ## 快速冪 ### Binary Exponentiation ---- ## 目標 快速計算 $x^y$，其中 $y$ 為非負整數 ---- 原本我們在計算 $x^y$ 的時候呢，有一個最直觀且簡短的寫法，就是跑一個時間複雜度為 $O(y)$ 的迴圈 ```cpp= int ans = 1; for(int i = 1; i <= y; i++){ ans * = x; } cout << ans << "\n"; ``` 但是如果今天 $y$ 太大的時候，就會需要優化這個程式，需要讓他更快速的解決這個問題，於是就衍生出了快速冪的這個算法。 ---- 先把 y 換成二進位 以 $2^{13}$ 為例 $$ \begin{split} 13&= (1101)_2\\ &= 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0\\ &= 8 + 4 + 1\\ \end{split} $$ $$ \Rightarrow 2^{13} = 2^{8+4+1} = 2^8 \cdot 2^4 \cdot 2^1 $$ ---- 我們只要求出 $2^8, 2^4, 2^1$ 就好 也就是 $x^y$ 只需要求出每個目標的 $2^i$ 再做相加 時間是 $\log_2 y$ ，也就是 $y$ 的二進位編碼長度 ---- ## 圖解快速冪 快速冪簡單來說就是用二進位本身的機制，判斷每次到底要「跳」幾次 ---- ## 圖解快速冪 以下例子中，假設我們想要求 $7^7$，則我們知道 $7^7=7^{2^0+2^1+2^2}$ 透過二進位編碼，我們可以選擇每個 $2^i$ 要「跳」/「不跳」($0\text{ or }1$)  記住這個觀念，以後 **倍增法/LCA** 會再出現 <!-- .element: class="fragment" data-fragment-index="1" --> ---- ## 實作想法 考慮窮舉所有的 $2^i$ ($0\leq i \leq \log_2 y$)， 若 $y$ 相對應的 bit 是 $1$ 就將答案乘上 $2^i$ 否則答案不變 ---- ## 實作細節 - 可以用 $y$ & $1$ 來取最右那一位的值 - 每次配合 $y$ >>= $1$ 來跑完整個 $y$ 每一位 - 用 $\text{ans}$ 維護答案，初始化為 $1$ - 開 long long 處理 ---- ## 程式碼 ```cpp= typedef long long ll; // 方便簡寫 ll mypow(ll x, ll y) { ll ans = 1; // 記得這裡一定要設為 1 才有辦法乘 while (y) { // 當 y 的所有 bit 都判斷完就離開迴圈 if (y & 1) ans = ans * x; // 判斷每次要跳 / 不跳 x = x * x; // 每次把自己平方 y >>= 1; // 每次右移一格 } return ans; } ``` ---- ## 過程 以 $2^{13}$ 為例 : | 原本 $\text{ans}$ | $x$ | $y$| $y$ 的最右 | 計算後 $\text{ans}'$ | | -------- | -------- | -------- | -------- | -------- | | $1$ | $2^1$ | $1101$ | $1$ | $2^1=1\cdot2=2$ | | $2$ | $2^2$ | $110$ | $0$ | 不變 | | $2$ | $2^4$ | $11$ | $1$ | $2^4=2\cdot 2^4=32$ | | $32$ | $2^8$ | $1$ | $1$ | $2^8=32\cdot 2^4=8192$ | 算出 $2^{13}$ 的答案為 $8192$ ---- ## 溢位處理 如果數字太大的話，很有可能會超過 long long 的範圍 因此許多題目會要我們把結果 mod 一個數字 ---- ## 加入 mod 後的程式碼 ```cpp= const ll MOD = 1e9 + 7; // 1000000007 是個質數 ll mypow(ll x, ll y){ ll ans = 1; while(y){ if(y & 1) ans = (ans * x) % MOD; // 這裡 % MOD x = (x * x) % MOD; // 這裡 % MOD y >>= 1; } return ans; } ``` ---- ## mod與乘法的交換律 為什麼我們在實作的過程中可以邊 mod 邊乘，答案還會對? 根據餘式定理 : $$ a = (c_1 \times m) + r_1, \quad b = (c_2 \times m) + r_2 $$ 將 $a$ 與 $b$ 帶入 $(a\times b) \% m$，並根據 mod 運算的分配律: $$ \begin{split} (a \times b) \% m &= ((c_1 \times m) \times (c_2 \times m)) \% m\\ &+((c_1 \times m) \times r_2)\%m +((c_2 \times m) \times r_1)\% m\\ &+ (r_1 \times r_2) \% m \end{split} $$ ---- 根據定義，由於 $$ r_1=a\%m, r_2=b\%m $$ 又我們發現上一頁有些項可以被 $m$ 整除，因此我們得到以下結論 $$ \begin{split} (a \times b) \% m &= \cancel{((c_1 \times m) \times (c_2 \times m)) \% m}\\ &+\cancel{((c_1 \times m) \times r_2)\% m} +\cancel{((c_2 \times m) \times r_1)\% m}\\ &+ (r_1 \times r_2) \% m=((a \% m) \times (b \% m)) \% m \end{split} $$ ---- 簡單來說就是: $$ \text{先乘後 %}m=\text{先 %}m\text{ 後乘} $$ 所以我們的程式碼可以這樣弄 ---- 換成 $2$ 進位，只需要計算 $\log_2 y$ 次 當要計算 $x^y$ ，$y$ 到 $10^{18}$ 的時候 $\log_2 10^{18} \approx 60$ 只需做 $60$ 次就可以算出 $x^{10^{18}}$ --- ## 作業 & 練習時間 https://vjudge.net/contest/756605 ---- Any questions?