Implement pow(x, n).
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