[LeetCode] 50 power (x, n)

• Problem: power (x, n), x為正整數
• Solution:
• 一種是 iteratively 的用 while loop, count down n 的值, 每次乘上 x
• 另一種直覺的是用 recursive, 但注意指數可以用平方來加速, 即 x^2 = x * x
• Note: 注意各 boundary, e.g. n < 0, n = MIN_INT 及 unsigned/signed 切換等 case

class Solution {
public:
    double myPow(double x, int n) {
        if (0 == n) return 1;
        if (1 == n) return x;

        double sq = myPow(x, n/2);
        if (INT_MIN == n)
            return sq * sq;
        if (0 > n) return 1.0 / myPow(x, abs((unsigned int)-n));

        if (0 == n % 2)
            return sq * sq;
        else
            return x * sq * sq;
    }
};