【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++