[LeetCode]乘冪 Pow(x, n)

題目描述

實作pow(x, n)，用來計算x的n次方，即xn。

原題網址

輸入格式

• -100.0 < x < 100.0
• -231 <= n <= 231 - 1
• -104 <= xn <= 104

範例輸入1

範例輸出1

範例輸入2

範例輸出2

範例輸入3

範例輸出3

額外解釋3

#{{{
2^{-2} = { 1 \over {2^2} } = { 1 \over 4 } = 0.25
}}}#

題解

這題雖然可以直接使用程式語言內建的pow函數來完成，但不建議。

若要自己實作出powi這種指數是整數的函數，直覺的方式就是，若指數是正整數，就用1連續乘上底數，次數即為該正整數；若指數為負整數，就先把底數改成其自身的倒數，再把負整數乘上-1變成正整數，接著指數為用正整數的處理方式來計算。

但是，這樣單純連乘的做法效能是很差的。比較好的做法是，先提取指數的2的因數，將底數進行平方處理，直到指數沒有2的倍數。例如，#{{2^{40} = 4^{20} = 8^{10} = 16^{5}}}#，如此一來，原本要進行的#{{24}}#次乘法，縮減為只要進行#{{3 + 5 = 8}}#次即可。

但是當指數為奇數的時候，就會需要先進行額外提取的動作。例如：

#{{{2^{43} = 2 \times 2^{42} = 2 \times 4^{21} = 2 \times 4 \times 4^{20} = 8 \times 8^{10} = 8 \times 16^{5}}}}#

在程式實作上，進行「指數除以2」的動作前，要先判斷此時的指數是否為奇數，如果是的話，就先將連乘結果先乘上此時的底數。之後才進行底數平方以及「指數除以2」的處理。

impl Solution {
    pub fn my_pow(mut x: f64, n: i32) -> f64 {
        let mut n = n as i64;
        let mut ans = 1.0;

        if n < 0 {
            n = -n;
            x = 1.0 / x;
        }

        while n > 0 {
            if n & 1 == 1 {
                ans *= x;
            }

            x *= x;

            n >>= 1;
        }

        ans
    }
}

const myPow = (x: number, n: number): number => {
    let ans = 1.0;

    if (n < 0) {
        n = -n;
        x = 1.0 / x;
    }

    while (n > 0) {
        if ((n & 1) === 1) {
            ans *= x;
        }

        x *= x;

        n >>>= 1;
    }

    return ans;
};