---
title : 快速冪(上)
tags : article
---

# 前導：位元運算子(Bitwise operator)

在C/C++，一共有6個位元運算子：
AND`&`、OR`|` 、XOR`^`、NOT(補數)`~`、左移`<<`、右移`>>`
<font color= red>(需與`&&`、`||`、`!` 這3個「邏輯運算子」做區分)</font>

> C++的cin與cout同樣使用左移和右移運算子，但並非位元運算子的功能，
是由於cin和cout被<font color= blue>運算子重載(operator overloading)</font>的關係(定義一個運算子是要做什麼的)。
再舉例來說：string的加法也是利用了運算子重載以實現字串拼接。
> - 運算子重載wiki簡短介紹：https://zh.wikipedia.org/wiki/%E8%BF%90%E7%AE%97%E7%AC%A6%E9%87%8D%E8%BD%BD
> - 運算子重載的好文推薦：http://tw.gitbook.net/cplusplus/cpp_overloading.html]

其位元運算的運算法的方式，即是把10進位轉成2進位後，再與各別的2進位位數做位元運算：

7 & 49 == 54   //000111 AND 110001 == 000001
35 ^ 18 == 49  //100011 XOR 010010 == 110001
7 << 3 == 56   //111 左移3次 == 111000
37 >> 2 == 9   //100101 右移2次 == 1001

位元運算子如同加減乘除，也可以寫成等於的計算形式：

a &= 7;
a <<= 1;

<font color= red>>>！以下請特別注意！<<</font>
要使用long long int與純數字進行位元運算的時候，
請務必注意要使用轉換型態(純數字會將型態辨別成int，而非long long int)：

long long int a = 50;
a &= 27LL;                // way 1
a >>= (long long int)3;   // way 2

- 位元運算：https://openhome.cc/Gossip/CppGossip/LogicalBitwise.html
- Geeks介紹：https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

---

# 前導：模算數與模除

- ### 模算數(modular arithmetic)
在數學表達式，<font color= blue>模算數</font>的表達式為 <font color= blue>$a ≡ b \pmod n$</font>，可以理解為a與b為同餘(有共同餘數)，
以下模算數敘述為等價：
(1) a-b為n的倍數 (n整除a-b)
(2) a除以n的餘數與b除以n的餘數相等 (a%n = b%n)

`ex.` $38 ≡ 14 ≡ 2 ≡ -10\pmod {12}$

於a,b為<font color= red>整數</font>、n為<font color= red>正整數</font>時，若 $a_1≡b_1 \pmod n$ 且 $a_2≡b_2 \pmod n$，則滿足以下定律：
1. $a_1+a_2 ≡ b_1+b_2 \pmod n$
2. $a_1×a_2 ≡ b_1×b_2 \pmod n$

- ### 模除(modulo / modulus)
在程式來看，其取餘數的運算規則會與模算數的運算規則相當，
通常會將「模除」這個行為以「a mod b」這個方式表示，其意思在程式與「a % b」相當。

於a,b為<font color= red>整數</font>、n為<font color= red>正整數</font>時，則滿足以下定律：
1. $(a+b)\%n = (a\%n + b\%n)\%n$
2. $(a×b)\%n = (a\%n×b\%n)\%n$

- wiki介紹 : https://zh.wikipedia.org/wiki/%E6%A8%A1%E7%AE%97%E6%95%B8
- 好文推薦 : https://ithelp.ithome.com.tw/articles/10205727

---

# 次方快速冪(Fast Power)
``(Wiki又稱此為平方求冪(exponentiating by squaring))``

已經知道，任何一個十進位數都可以被轉換成二進位數
`ex.` $(97)_{10}=(1100001)_{2}=1+32+64$

且指數運算滿足：$a^{b+c}=a^{b}·a^{c}$，故可將次方數 $a^b$ 以二進位的組合來看
`ex.` $7^{97}=7^{1100001_{_2}}=7^{1}·7^{32}·7^{64}$
`ex.` $7^{31}=7^{11111_{_2}}=7^{1}·7^{2}·7^{4}·7^{8}·7^{16}$

(印出倒置二進位的函式)：

void print_binary(int a){
    while(a>0){
        printf("%d",a&1);
        a>>=1;
    }
}
//input : 4
//output: 001

計算快速冪的時候，用倒過來表示的形式會比較好算(4=001)，可以想看看為什麼，
接著嘗試利用快速冪計算次方的方式，寫出一個函式吧。(可以同時考慮位數過大，要取餘數的情況)
`ex.` $3^{987654321}\mod 10000007$

int pow(int a, int n, int mod);        //calculate (a^n)%mod

為什麼要用快速冪算法呢?
可以稍微想想，普通的迴圈要計算次方的話，如果是 $a^n$，就要跑迴圈 $n$ 次(做 $n$ 次乘法)，
但如果是用快速冪的算法來計算次方的話，只需要跑 $\log_2(n)$ 次乘法就好，
我們可以嘗試比較這兩個數字，
當 $n=10000000$時，$\log_2(n)=23.2534966642$，可以看出 $\log_2(n)$ 遠小於 $n$。

下篇的快速冪會稍微簡短說明「時間複雜度(Big-O)」的觀念，以及「矩陣快速冪」。

---

# Problem set

### 次方快速冪題目選：
1. ZeroJudge：[d636 - 大爆炸](https://zerojudge.tw/ShowProblem?problemid=d636)
2. UVa：[374 - Big Mod](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=310)
3. POJ：[1995 - Raising Modulo Numbers](http://poj.org/problem?id=1995)
4. LeetCode：[50 - Pow(x,n)](https://leetcode.com/problems/powx-n/)

### Hints
1. 計算快速冪時不用考慮會出現溢位的問題(計算範圍都在65535以下)，請記得要「模算數」。
3. 與上一題幾乎相同，但需要注意相乘後++可能++會有溢位的問題。
4. 計算次方數之和模除後的值，需仔細考慮模除(%)的配置。
5. 次方的底數部分從整數變成小數，並且次方部分會出現小數點，
題目無要求取餘數，無需考慮任何的模算數。(註：小數點運算是不能用%的)

---
# 後記
想必有些人應該知道，在C/C++的<math.h>有pow的這函式(拿來計算次方的)，
但以下再三強調：

<font color=red>！！計算整數次方數的次方運算時，請不要使用內建的pow函式！！
！！計算整數次方數的次方運算時，請不要使用內建的pow函式！！
！！計算整數次方數的次方運算時，請不要使用內建的pow函式！！</font>

內建的pow函式的速度極慢，如果要使用的話請務必自行寫一個pow的函式。
文章參考：[StackOverflow - Why is pow(int, int) so slow?](https://stackoverflow.com/questions/41072787/why-is-powint-int-so-slow/41072811)

希望日後新版的C++能把pow的函式給加速(#

###### posted date: `2021.1.29`