Pow(x, n)

medium binary exponentiation math

Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Inputx = 2.0, n = 10

Output1024.0

Walk the bits of n. Maintain a running product; each step squares x and, when the current bit is 1, multiplies the answer by x.

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    ans = 1.0
    while n:
        if n & 1:
            ans *= x
        x *= x
        n >>= 1
    return ans

function myPow(x, n) {
  if (n < 0) { x = 1 / x; n = -n; }
  let ans = 1;
  while (n) {
    if (n & 1) ans *= x;
    x *= x;
    n = Math.floor(n / 2);
  }
  return ans;
}

class Solution {
    public double myPow(double x, int n) {
        long m = n;
        if (m < 0) { x = 1 / x; m = -m; }
        double ans = 1.0;
        while (m > 0) {
            if ((m & 1) == 1) ans *= x;
            x *= x;
            m >>= 1;
        }
        return ans;
    }
}

double myPow(double x, int n) {
    long m = n;
    if (m < 0) { x = 1 / x; m = -m; }
    double ans = 1.0;
    while (m) {
        if (m & 1) ans *= x;
        x *= x;
        m >>= 1;
    }
    return ans;
}

Explanation

Multiplying x by itself n times works but takes n steps. The faster trick, called exponentiation by squaring, computes the same result in only about log n steps by looking at the binary digits of n.

The idea rests on a simple fact: any power can be built from repeated squaring. We keep a running base that doubles its exponent each round (x, then x^2, then x^4, ...). Whenever the current bit of n is 1, that power belongs in the answer, so we multiply ans by the current base.

Each loop does two things: if n & 1 is set, do ans *= x; then always square the base with x *= x and shift to the next bit with n >>= 1. If n is negative, we first flip x to 1/x and make n positive.

Example: x = 2, n = 10. In binary 10 = 1010. The set bits are at positions 1 and 3, which stand for 2^2 = 4 and 2^8 = 256. Multiplying those gives 4 * 256 = 1024, exactly 2^10.

Because we process one bit per step and n has only about log n bits, this is dramatically faster than naive repeated multiplication.

Time: O(log n) Space: O(1)