Integer Power Using Exponentiation

medium binary exponentiation math

Problem

Compute xⁿ where x is a real number and n is an integer, possibly negative. Multiplication is the only operation allowed.

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;
}

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