50. Pow(x, n)

三目运算符 Java ternary operator

Version #2 Iterative Bit Manipulation
一直没有绕过来的地方是每一次对temp 进行什么样的操作
5 = (101)2 = 1* 2^2 + 0* 2^1 + 1* 2^0
x^5 = x^(2^2) * x^(2^0)
对于bit "i"
result = result * x^(2^i)
这里的 x^(2^i) 是 temp

i = 0, temp = x;
i = 1, temp = x^2;
i = 2, temp = x^4
i = 3, temp = x^(2^3) = x^8
so for every increment of i, temp = temp^2;

Time Complexity
Outer loop -> at most 32 operaton

"Yes, since you're dividing N by 2 every iteration that's why it is O(Log N). However, since N is a fixed number of bits (32) you could view it as O(1) where the maximum number iterations is 32. Hope this helps."

55.54 %
class Solution { public double myPow(double x, int n) { // n = bit31 * 2^31 + bit30 * 2^30 +... long absN = Math.abs((long)n); double result = 1.0; double temp = x; while (absN != 0) { if ((absN & 1) != 0) result *= temp; temp *= temp; absN >>= 1; } return (n < 0) ? 1.0 / result : result; } }


二刷
version2
class Solution {
    public double myPow(double x, int n) {
        // x = 2, n = 10
        // n = (1011) = (1*2^3 + 0*2^2 + 1*2^1 + 1*2^0);
        // x^n = x^(1*2^3 + 0*2^2 + 1*2^1 + 1*2^0)  =x^(2^3)* x^(2^1) * x^(2^0)
        if (n < 0) {
            return 1 / x * myPow(1 / x, -(n + 1));
        }
        double result = 1;
        // e.g. n = 111
        //      x
        //     x * x = x^2
        //    x * x * x * x = x^4
        //                         x^8
        while(n != 0) {
            result *= (n & 1) == 0 ? 1 : x;
            n >>= 1;
            x *= x;
        }
        return result;
    }

}






Version #1 Recursion
Time O(logn)

LeetCode Version
处理n < 0 的情况很头疼
如果有n = Integer.MIN_VALUE，-n会出错
所以先对n 取 n/2，就不会overflow了
 92.27 %
class Solution { public double myPow(double x, int n) { if (n == 0) return 1; int t = n / 2; if (n < 0) { x = 1 / x; t = -t; } double temp = myPow(x, t); return (n % 2 == 0) ? temp * temp : x * temp * temp; } }

myPow Version

public int myPow(int x, int n) {

if (n == 0) return 1;

if (n == 1)  return x;

int temp = myPow(x, n / 2);

return n % 2 == 0 ? temp * temp : temp * temp * x;

}