---
# System prepended metadata

title: 快速冪

---

# 快速冪
>快速冪是一種能在$O(\log n)$時間內算出$a^n$的技巧
背後的原理是將次方以二進制表示
>
舉例來說如果今天你要算$5^{11}$，原本你可能會算$5\times5\times5\times5....$乘到11，做n次。

快速冪則是將式子換成$5^8 \times 5^2 \times 5^1$ 也就是下面這個表格

| $2^0$ | $2^1$ | $2^2$ | $2^3$ |
| ----- | ----- | ----- | ----- |
|    1   |    1   |    0   |   1    |
>5的次方
>
換成這種形式的好處是原本要做n次的運算，瞬間就變為$O(\log n)$

## 程式碼:

### 方法一:遞迴
```c++=
int quickpow(int x, int n) {
  if (n == 0) return 1;
  int res = quickpow(x, n / 2);
  if (n % 2) //基數
    return res * res * x;
  else //偶數
    return res * res;
}
``` 
### 方法二:迴圈
```c++=
int quickpow(int x, int n) {
  int res = 1;
  while (n > 0) {
    if (n & 1) res = res * x; //  基數
    x = x * x;
    n >>= 1; //  n /= 2
  }
  return res;
}
``` 
