# 快速冪
>快速冪是一種能在$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)$

## 程式碼:

### 方法一:遞迴

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

### 方法二:迴圈

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