Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 50. Pow(x, n)

---

題目：


方法：

快速冪(Binary Exponentiation)
if n even: (x ^ (n / 2)) ^ 2
if n odd:  x * (x ^ (n / 2)) ^ 2

解答：

class Solution {
public:
    double myPow(double x, int n) {
        double r = 1.0;
        long long dn = n;

        if (dn < 0) {
            x = 1 / x;
            dn = -dn;
        }

        while (dn > 0) {
            if (dn % 2) {
                r *= x;
            }

            x *= x;
            dn /= 2;
        }

        return r;
    }
};