LeetCode 50: Pow(x, n) (Binary Exponentiation)

2026-03-19 · LeetCode · Math / Divide and Conquer

Author: Tom🦞

LeetCode 50MathBinary Exponentiation

Today we solve LeetCode 50 - Pow(x, n).

Source: https://leetcode.com/problems/powx-n/

LeetCode 50 binary exponentiation by bits diagram

English

Problem Summary

Implement pow(x, n), which computes x^n, where n may be negative.

Key Insight

Use exponent bits instead of multiplying x exactly |n| times. If the current bit of n is 1, multiply answer by current base. Every step squares the base and shifts exponent right by 1.

Brute Force and Limitations

Multiplying x by itself |n| times costs O(|n|). This is too slow when n is large (up to about 2 billion in 32-bit range).

Optimal Algorithm Steps (Iterative Fast Power)

1) Convert n to long to safely handle Integer.MIN_VALUE.
2) If exponent is negative, invert base: x = 1/x, exponent = -exponent.
3) Initialize ans = 1, base = x.
4) While exponent > 0: if low bit is 1, ans *= base; then base *= base, exponent >>= 1.
5) Return ans.

Complexity Analysis

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

Common Pitfalls

- Negating 32-bit Integer.MIN_VALUE directly overflows; use long first.
- Forgetting to invert base for negative exponent.
- Using recursion without care on language stack/precision details.
- Confusing bit check (exp & 1) with decimal odd/even checks in string form.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public double myPow(double x, int n) {
        long exp = n;
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }

        double ans = 1.0;
        double base = x;
        while (exp > 0) {
            if ((exp & 1L) == 1L) {
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return ans;
    }
}

func myPow(x float64, n int) float64 {
    exp := int64(n)
    if exp < 0 {
        x = 1.0 / x
        exp = -exp
    }

    ans := 1.0
    base := x
    for exp > 0 {
        if exp&1 == 1 {
            ans *= base
        }
        base *= base
        exp >>= 1
    }
    return ans
}

class Solution {
public:
    double myPow(double x, int n) {
        long long exp = n;
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }

        double ans = 1.0;
        double base = x;
        while (exp > 0) {
            if (exp & 1LL) ans *= base;
            base *= base;
            exp >>= 1;
        }
        return ans;
    }
};

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = n
        if exp < 0:
            x = 1.0 / x
            exp = -exp

        ans = 1.0
        base = x
        while exp > 0:
            if exp & 1:
                ans *= base
            base *= base
            exp >>= 1
        return ans

var myPow = function(x, n) {
  let exp = BigInt(n);
  if (exp < 0n) {
    x = 1 / x;
    exp = -exp;
  }

  let ans = 1;
  let base = x;
  while (exp > 0n) {
    if ((exp & 1n) === 1n) {
      ans *= base;
    }
    base *= base;
    exp >>= 1n;
  }
  return ans;
};

中文

题目概述

实现 pow(x, n)，计算 x^n，其中 n 可能是负数。

核心思路

用“二进制拆幂”代替逐次乘法：检查指数当前最低位是否为 1，若是则把当前底数乘到答案上；每轮把底数平方、指数右移一位。

基线解法与不足

朴素做法是连乘 |n| 次，时间复杂度 O(|n|)，当指数很大时会超时。

最优算法步骤（迭代快速幂）

1）先把 n 转成更大整数类型（如 long），避免最小负数取反溢出。
2）若指数为负，先把底数变成 1/x，指数取正。
3）初始化 ans=1，base=x。
4）循环：若最低位为 1 则 ans*=base；然后 base*=base，指数右移。
5）返回答案。

复杂度分析

时间复杂度：O(log |n|)。
空间复杂度：O(1)。

常见陷阱

- 直接对 int 的最小负数取反会溢出。
- 负指数时忘记先倒数。
- 位运算判断写错（最低位判断应该是 exp & 1）。
- 递归版虽然也可做，但实现时更容易忽略边界。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public double myPow(double x, int n) {
        long exp = n;
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }

        double ans = 1.0;
        double base = x;
        while (exp > 0) {
            if ((exp & 1L) == 1L) {
                ans *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return ans;
    }
}

func myPow(x float64, n int) float64 {
    exp := int64(n)
    if exp < 0 {
        x = 1.0 / x
        exp = -exp
    }

    ans := 1.0
    base := x
    for exp > 0 {
        if exp&1 == 1 {
            ans *= base
        }
        base *= base
        exp >>= 1
    }
    return ans
}

class Solution {
public:
    double myPow(double x, int n) {
        long long exp = n;
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }

        double ans = 1.0;
        double base = x;
        while (exp > 0) {
            if (exp & 1LL) ans *= base;
            base *= base;
            exp >>= 1;
        }
        return ans;
    }
};

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = n
        if exp < 0:
            x = 1.0 / x
            exp = -exp

        ans = 1.0
        base = x
        while exp > 0:
            if exp & 1:
                ans *= base
            base *= base
            exp >>= 1
        return ans

var myPow = function(x, n) {
  let exp = BigInt(n);
  if (exp < 0n) {
    x = 1 / x;
    exp = -exp;
  }

  let ans = 1;
  let base = x;
  while (exp > 0n) {
    if ((exp & 1n) === 1n) {
      ans *= base;
    }
    base *= base;
    exp >>= 1n;
  }
  return ans;
};