<style>
.reveal .slides {
text-align: left;
font-size:30px
}
</style>
## 位元運算 & 快速冪
10/23 preTraining
----
- 位元運算
- 快速冪
---
### 位元運算
位元運算是對二進位的 0 和 1 做一些處理，然後會出現一些性質和用途。
----
二進位理所當然就只有 true(1) 跟 false(0)，以下是位元運算示範操作
```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
```
----
### XOR運算
因為 XOR 太多常用性質，所以特別拿出來講。
先來幾個基本原則（bitwise xor 的符號一樣用 ⊕）：
1. A ⊕ B = B ⊕ A，(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)，也就是運算順序不影響結果(有交換律和結合律)。
2. A ⊕ A = 0
3. 若 A ⊕ B = C，則 A ⊕ C = B
4. A ⊕ 0 = A
----
### 左移 右移 運算
C++程式裡使用"<<"與">>"來表示，表示為位元左移(右移)一格
左移時最左邊會補上 0
而右移時最右邊位元會被移除
```=
9=1001 9<<1 = 10010 = 18
15=1111 15>>1 = 111 = 7
常見用法
(x>>1) 快速除2 以及 (x<<1) 和 (x<<1)|1 左子節點和右子節點
```
----
### 補數運算
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
|| <span class="spoiler-text"> 每個bit拆開來即可發現規律 </span> ||
----
1 最低的'1'位元
```cpp=
x & -x
```
根據二的補數，-x 為 ~x + 1。因此在這先將 -x 拆開為 ~x + 1 來討論。
x 中最低位的位元 1 經過 not 運算後，將在 ~x 中變為最低位的位元 0。
因此對 ~x 加上 1 後，最低位的位元 0 重新變為位元 1，且其後的位元都將被設定為 0。
2 檢查冪次
是否為二的冪次
```cpp=
(x & -x) == x
```
由於若你為二的冪次，則該數字只會有一個位元(也是最高位元)
----
## 實作例題講解
練習 1 --- XOR 練習
```cpp=
x^=y^=x^=y
```
請問 x,y 各為多少?(用 x 跟 y 表示)
----
拆開來看即為
```cpp=
x = x ^ y;
y = y ^ x;
x = x ^ y;
```
答案為 x 為 y ,y 為 x (相等於 swap ( x , y ))
----
練習 2 --- 優先級的練習
```cpp=
cout<<(15>>1+2);
```
----
```cpp=
cout<< ( 15 >> 1 + 2 );
```
ans : 1
大多數的位元運算子的運算優先級都比較低，
因此此題的計算過程為 1 + 2 = 3 , 15(1111) >> 3 = 1.
所以你不確定優先級的時候最好都要加括號
----
練習 3 --- 常用的技巧
```cpp=
if(x & 1) return 1;
else return 0;
```
```cpp=
return (x & 1);
```
----
```cpp=
if(x&1) return 1;//(奇數)
else return 0;//(偶數)
```
判斷 x 的奇偶性 也是常見用法 (比較快)
由於一個數字的位元組成都是 2 的冪次方
因此 $2^n$ 只有在 n==1 的時候會影響到數字的奇偶性，
故只需要判斷最後一個位元
---
## 快速冪
* 快速計算 $x^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}$ 為例
$13$
$= 1101$
$= 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0$
$= 8 + 4 + 1$
$\to 2^{13} = 2^8 * 2^4 * 2^1$
----
因此，我們只要求出 $2^8, 2^4, 2^1$ 就好
也就是只需要求出每個目標的二的冪次在做相加，也就是 $\log N$ 次
----
## 實作
一樣以 $2^{13}$ 為例
$1101$ 就從最右邊的 bit 開始
判斷最右邊的 bit 是不是 $1$ 如果是 $1$ 則把答案乘上去
接著每次把 $x$ 平方
接著把整個右移一個，變成 $110$
因此一樣變成判斷最右邊的 bit 即可
$再右移\to 11$
$再右移\to 1$
一直做到 y 右移到 0 為止
----
## 過程
| x | y | 原本答案 | 計算後答案 |
| -------- | -------- | -------- | -------- |
| $2^1$ | 1101 | $2^0$ | $2^1$ |
| $2^2$ | 110 | $2^1$ | $2^1$ |
| $2^4$ | 11 | $2^1$ | $2^5$ |
| $2^8$ | 1 | $2^5$ | $2^{13}$ |
----
## 程式碼
```cpp=
long long mypow(long long x,long long y){
long long ans = 1;
while(y){
if( y&1 ) ans = ans * x;
x = x * x; //每次把自己平方
y >>= 1; //每次右移一格
}
return ans;
}
```
----
## 溢位處理
如果數字太大的話，很有可能會超過 long long 的範圍
因此許多題目會要我們把結果 mod 一個數字
----
## 加入 mod 後的程式碼
```cpp=
const ll MOD = 1e9 + 7;
long long mypow(long long x,long long y){
long long ans = 1;
while(y){
if( y&1 ) ans = (ans * x) % MOD;
x = (x * x) % MOD; //每次把自己平方
y >>= 1; //每次右移一格
}
return ans;
}
```
----
## mod與乘法的交換律
為什麼我們在實作的過程中可以邊 mod 邊乘?
在 $(A \times B) \% m$ 的情況下
$A = (C_1 \times m) + R_1$, $B = (C_2 \times m) + R_2$
$(A \times B) \% m = ((C_1 \times m) \times (C_2 \times m)) +((C_1 \times m) \times R_2) +((C_2 \times m) \times R_1)$
$+ (R_1 \times R_2) \% m$
我們可以發現上方的一行皆可以被 $m$ 整除，因此我們得到這樣的結論
$(A \times B) \% m = ((A \% m) \times (B \% m)) \% m$
----
換成 2 進位，只需要計算 $\log y$ 次
當要計算 $x^y$ ，$y$ 到 $10^{18}$ 的時候
$\log 10^{18} = 60$
只需做 60 次就可以算出 $x 的 10^{18}$ 次方
{"title":"bitwise & pow","description":"10/23 preTraining","contributors":"[{\"id\":\"08326fa4-ca9b-4ca9-873e-239ebe76662c\",\"add\":4644,\"del\":3,\"latestUpdatedAt\":1729647205283}]"}