---
type: slide
---

<style>
.reveal .slides {
text-align: left;
font-size:30px
}
</style>

## 位元運算 & 快速冪
10/23 preTraining

----

- 位元運算
- 快速冪

---

### 位元運算
位元運算是對二進位的 0 和 1 做一些處理，然後會出現一些性質和用途。

----

二進位理所當然就只有 true(1) 跟 false(0)，以下是位元運算示範操作

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，也就是裡面都是布林值

所以可以常常看到這種寫法

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'位元

    x & -x

根據二的補數，-x 為 ~x + 1。因此在這先將 -x 拆開為 ~x + 1 來討論。
x 中最低位的位元 1 經過 not 運算後，將在 ~x 中變為最低位的位元 0。
因此對 ~x 加上 1 後，最低位的位元 0 重新變為位元 1，且其後的位元都將被設定為 0。

2 檢查冪次
是否為二的冪次

    (x & -x) == x

由於若你為二的冪次，則該數字只會有一個位元(也是最高位元)

----

## 實作例題講解

練習 1 --- XOR 練習

    x^=y^=x^=y

請問 x,y 各為多少?(用 x 跟 y 表示)

----

拆開來看即為

x = x ^ y;
y = y ^ x;
x = x ^ y;

答案為 x 為 y ,y 為 x (相等於 swap ( x , y ))

----

練習 2 --- 優先級的練習

cout<<(15>>1+2);

----

cout<< ( 15 >> 1 + 2 );

ans : 1
大多數的位元運算子的運算優先級都比較低，
因此此題的計算過程為 1 + 2 = 3 , 15(1111) >> 3 = 1.
所以你不確定優先級的時候最好都要加括號

----

練習 3 --- 常用的技巧

if(x & 1) return 1;
else return 0;

return (x & 1);

----

if(x&1) return 1;//(奇數)
else return 0;//(偶數)

判斷 x 的奇偶性 也是常見用法 (比較快)
由於一個數字的位元組成都是 2 的冪次方
因此 $2^n$ 只有在 n==1 的時候會影響到數字的奇偶性，
故只需要判斷最後一個位元

---

## 快速冪

* 快速計算 $x^y$

----

原本我們在計算 $x^y$ 的時候呢，有一個最直觀且簡短的寫法，就是跑一個時間複雜度為 $O(y)$ 的迴圈

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}$ |

----

## 程式碼

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 後的程式碼

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}$ 次方