Thursday, April 30, 2015

[LeetCode] Pow(x, n)

Pow(x, n)

Implement pow(xn).
Solution: Bit Manipulation. The idea is that we look at the i-th bit of n, if it is 1, we multiple by x^{2^i}. 
Pay attention to the case where n is negative.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public double myPow(double x, int n) {
        boolean neg = false;
        if (n < 0) {
            n = -1 * n;
            neg = true;
        }
        double result = 1.0;
        double mul = x;
        int mask = 1;
        while (n > 0) {
            if ((n & mask) > 0) {
                result *= mul;
            }
            mul = mul * mul;
            n = n >> 1;
        }
        if (neg) {
            return 1.0 / result;
        }
        return result;
    }
}

No comments:

Post a Comment