剑指 Offer.16-数值的整数次方

题目链接

<剑指 Offer 16. 数值的整数次方>

问题描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

个人想法

使用快速幂，但不会快速幂算法…

官方解法

快速幂，将数字的指数看为二进制，循环遍历二进制位，当目前对应的二进制位为1时，将结果乘入res中，x在每次遍历中进行平方操作

注意：需要对指数为负数的情况进行处理

代码

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

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。