x 的指数

Posted on Sep 07, 2024 By ᵇᵒ

pow(x, n)

LeetCode 50

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

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

  • -100.0 < x < 100.0
  • \(-2^{31}\) <= n <= \(2^{31}-1\)
  • n is an integer.
  • Either x is not zero or n > 0.
  • \(-10^4\) <= \(x^n\) <= \(10^4\)

位运算

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

位运算“优化版”

int numberOfTrailingZeros(long n) {
    if (n == 0) return 0;
    float f = (float)(n & -n);
    return (*(unsigned int *)&f >> 23) - 0x7f;
}

double myPow(double x, int n) {
    long num = n;
    if(n < 0) {
        x = 1 / x;
        num = -num;
    }
    double pow = 1;
    int cnt = 0;
    while(num > 0) {
        int count = numberOfTrailingZeros(num);
        while(cnt < count) {
            x *= x;
            cnt++;
        }
        pow *= x;
        num = num & (num - 1);
    }
    return pow;
}

优化用到了一种 countOneBits 方案的思想，快速跳过 n 二进制中连续的 0，但是另一方面又需要用到跳过 0 的个数来计算乘积，所以最终并没有起到优化作用，反倒可能因统计 trailing zeros 而更加耗时。
不过不失为一种思路，特别是统计 trailing zeros 函数相当精妙(lowbit + bit hack)。