# 【LeetCode】 50. Pow(x, n)

## Description
> Implement `pow(x, n)`, which calculates `x` raised to the power `n` $(x^n)$.
> Note:
> * -100.0 < `x` < 100.0
> * `n` is a 32-bit signed integer, within the range `[−231, 231 − 1]`

> 實作 pow(x, n)，也就是計算`x`的`n`次方$(x^n)$。
> 注意：
> * -100.0 < `x` < 100.0
> * `n` 是三十二位元的有號整數，其範圍在 `[−231, 231 − 1]`

## Example:

Example 1:

Input: 2.00000, 10
Output: 1024.00000


Example 2:

Input: 2.10000, 3
Output: 9.26100


Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

## Solution

* 這題要實作pow()運算，你如果直接`return pow(x, n);`也會過，但這樣就沒有意義了XD
* 我們所使用到的技巧叫做`Square and multiply`，簡單來說是將`n`的部分藉由自己乘自己來大幅加速。
* 舉個例子，`2^9`我們可以想成`2*2*2*2*2*2*2*2*2` = `8`次乘法。
* 但我們可以先算出 `2*2=4`，然後將式子改為`2*4*4*4*4` = `5`次乘法。
* 再更進一步，我們還可以先算好`4*4=16`，最後變為`2*16*16` = `4`次乘法。
* 那麼，我們要怎麼知道要如何計算才能加速呢？
1. 首先，宣告一個新的數字`v = 1`去存結果，並將`n`想成是二進制碼(`9 = 1001`)
2. 接著判斷最低位元：如果是`1`，`v *= x`
3. 接著將`n`往右位移，並將`x *= x`。
4. 重複2.直至`n = 0`。
* 演算法的部分大致上就這樣，其原理就請自行google `Square and multiply`了，其實並不難理解。
* 如果`x`為整數的情況下，該演算法還可以加入取餘數的功能，讓整體速度更加提升。
* 不過這題用不到也不能用。
---
* 除了上面的演算法之外，這題還要處理幾個問題：
* `n`可能是負數，此時只需要將`n`轉回正數，並將`v *= x`改為`v /= x`即可。
* 然後要注意`n`是否超出範圍，適時的轉換型態或其他處理。

### Code

class Solution {
public:
    double myPow(double x, int n) {
        double value = 1;
        long nn = n;
        if(nn < 0)
        {
            nn *= -1;
            while (nn)
            {
                if (nn & 1)
                    value /= x;
                nn = nn >> 1;
                x *= x;
            }
        }
        else
            while (nn)
            {
                if (nn & 1)
                    value *= x;
                nn = nn >> 1;
                x *= x;
            }
        return value;
    }
};

###### tags: `LeetCode` `C++`