Implement pow(x, n)

更新时间：2022-05-09 04:00:46

问题：

实现次方运算

Implement pow(x, n).

解法：

Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 << i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<<i)). The loop executes for a maximum of log(n) times.

n还大于0的时候，每次循环x都在平方。遇到位为1的时候，把x乘进去。

Java代码：

    public static double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                return 1.0 / (myPow(x, Integer.MAX_VALUE)*x);
            } else {
                return 1.0 / (myPow(x,-n));
            }
        }
        double res = 1.0;
        for (;n > 0;x *= x,n>>=1) {
            if ((n & 1) > 0) {
                res *= x;
            }
        }
        return res;
    }

    public static double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                return 1.0 / (myPow(x, Integer.MAX_VALUE)*x);
            } else {
                return 1.0 / (myPow(x,-n));
            }
        }
        double res = 1.0;
        while (n > 0) {
            if ((n & 1) > 0) {
                res *= x;
            }
            x *= x;
            n>>=1;
        }
        return res;
    }

上一篇 : ：Subsets下一篇 : Sqrt(x)

Implement pow(x, n)

相关阅读

推荐文章