当前位置：
  1. 首页
  2. 剑指offer刷题第七期
  3. 问题详情

【位运算专题】剑指 Offer 16. 数值的整数次方

本问题对应课程链接：剑指offer刷题第七期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
110 11

共以下 11 个回答

  • Renasc 普通 2024年12月29日 下午1:52

    时间复杂度O(logN), 空间复杂度O(1)

    class Solution {
    public double myPow(double x, int n) {
        double res = 1; // 保存结果
        long y = n; // 取值

        // 如果指数为负数，则取指数的绝对值，并将取底数的倒数
        if (y < 0) {
            y = -y;
            x = 1 / x;
        }

        while (y > 0) {
            // 按照二进制的方式，如果当前位为1，则乘以对应的x^n
            if (y % 2 == 1) {
                res *= x;
            }

            x = x * x;
            y = y / 2;  // y右移
        }

        return res;
    }
}
    0 赞同 0 条回复
  • 陆狗陆狗 普通 2024年12月11日 下午10:25

    解题思路
    – 常规思维
    – 6^10= 6^(2+8)=6^26^8
    – 可以通过6^1-》6^2 -》 6^4 加快计算速度（无需计算到6^7）
    – 问题变成了2,8如何获取到？
    – 比如10%2的余数是0，说明6^1不存在
    – 5%2的余数是1，说明6^2存在（6^2=6^1    6^1）；
    – 2%2的余数是1，说明6^4存在（6^4=6^26^2）
    总结：【余数是否为1，表示是否要去    sum里面；但是6^1-》6^2-》6^4的递增过程不收到余数是否为1的影响】
    – 位运算思维
    – 问题变成了2,8如何获取到？ 比如10的二进制是1010【】
    – 1010 & 1 =0，说明最右边位是0；
    – 1010右移1位（1010>>1变成101），101&1=1，说明此时是1
    – 101右移1位（101>>1变成10），10&1=0，说明此时是0
    – 10右移1位（10>>1变成1），1&1=1，说明此时是1
    总结：【余数是否为1，用 n &1 是否等于1去完成；/2 使用 n>>1去完成 】
    【题解1】纯思路，非位运算版本

    class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long y = n;
        if(n < 0){
            y = -y;
            x = 1 / x;
        }
        while(y > 0){
            if(y % 2 == 1){
                res = res * x;
            }

            x = x * x;
            y = y / 2;
        }
        return res;
    }
}

    【题解2】思路同题解1，位运算版本

    class Solution {
    public double myPow(double x, int n) {
        // 【错误点1】不转换成long，会导致 n = -2147483648，(负数的绝对值是比正数要大1位的)
        // 执行 n = -n 时，-2147483648 不能被直接取反，因为其绝对值超出了 int 类型的表示范围。结果，n 仍然是 -2147483648
        long N=n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        // 6^7= 6^(1+2+4)=6^1*6^2*6^4
        // 可以通过6^1-》6^2 -》 6^4 加快计算速度（无需计算到6^7）
        // 问题变成了1,2,4如何获取到？ 比如7的二进制是110
        // 110 & 1 =0，说明最右边位是0；110右移1位，110>>1变成11，11&1=1，说明此时是1
        double sum = 1;
        double tmpt = x;
        while (N != 0) {
            if ((N & 1) == 1) {
                sum = sum * tmpt;
            }
            N = N >> 1;
            tmpt = tmpt * tmpt;
        }
        return sum;
    }
}
    • 错误点1：不转换成long，会导致 n = -2147483648，(负数的绝对值是比正数要大1位的)
      执行 n = -n 时，-2147483648 不能被直接取反，因为其绝对值超出了 int 类型的表示范围。结果，n 仍然是 -2147483648
    0 赞同 0 条回复
  • Xiang. 永久会员 2024年12月11日 上午9:30

    class Solution {
    public double myPow(double x, int n) {
    long N=n;
    if (N < 0) {
    N=-N;
    x=1/x;
    }
    double res=1.0;
    while(N>0){
    if(N%21){
    res=resx;
    }
    x=x    x;
    N=N/2;
    }
    return res;
    }
    }\
    时间复杂度：O（n）
    空间复杂度：O（1）

    0 赞同 0 条回复
  • 秋山丽奈 普通 2024年12月10日 下午8:58

    思路：参考力扣题解 使用 快速幂 计算

    class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}
    0 赞同 0 条回复
  • Aatorx 永久会员 2024年12月9日 下午5:18 
    class Solution {
public:
    double myPow(double x, int n) {
        double res = 1.0;
        long b = n;
        if (x == 0.0){
            return 0.0;
        }
        if (b == 0.0) {
            return 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;
    }
};

    将n保存为long防止负数时数值溢出。
    时间复杂度O(logN)，空间复杂度O(1)。

    0 赞同 0 条回复
  • lQl 永久会员 2024年12月9日 下午3:37 
    class Solution {
    public double myPow(double x, int n) {
        if (x == 0.0f)
            return 0.0d;
        long b = n;
        double ans = 1;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            if ((b & 1) == 1) {
                ans *= x;
            }
            x *= x;
            b >>= 1;
        }
        return ans;
    }
}

    时间复杂度O(logN)
    空间复杂度O(1)

    0 赞同 0 条回复
  • 月下足迹 普通 2024年12月9日 上午11:28

    class Solution {
    public double myPow(double x, int n) {
    long exp = n; // 转换为 long，避免溢出
    if (exp < 0) {
    x = 1 / x;
    exp = -exp;
    }

        double result = 1.0; // 初始化结果为 1
    double currentProduct = x; // 当前底数

    while (exp != 0) {
        if ((exp & 1) == 1) { // 检查当前指数最低位是否为 1
            result *= currentProduct; // 如果为 1，将当前底数乘入结果
        }
        currentProduct *= currentProduct; // 底数平方
        exp >>= 1; // 右移，处理下一个次方
    }

    return result;
}

    }

    0 赞同 0 条回复
  • Kisara 普通 2024年12月9日 上午12:24

    int类型溢出问题
    递归解法，未用位运算

    class Solution {
    public double myPow(double x, int n) {
        long N=n;
        if(n<0) return 1.0/solve(x,-n);
        else return solve(x,n);
    }
    public double solve(double x,long n){
        if(n==0) return 1.0;
        double y=solve(x,n/2);
        if(n%2==0) return y*y;
        else return y*y*x;
    }
}

    Ologn Ologn

    位运算解法 空间复杂度低

    class Solution {
    public double myPow(double x, int n) {
        long N=n;
        if(N<0) return 1.0/solve(x,-N);
        else return solve(x,N);
    }
    public double solve(double x,long n){
        double ans=1.0;
        //贡献值
        double x_contribute=x;
        while(n>0){
            if(n%2==1){
                //如果二进制表示最低位是1就乘入结果
                ans*=x_contribute;
            }
            //每次循环都把贡献值平方
            x_contribute*=x_contribute;
            //更新最低位，直接除2抛弃最低值
            n=n/2;

        }
        return ans;
    }
}

    Ologn o1

    0 赞同 0 条回复
  • 晓宇 普通 2024年12月8日 下午3:31 
    class Solution {
public:
    double myPow(double x, int n) {
        double ans = 1;
        long y = n;  // 不能用 int  2147483648  溢出
        if(n < 0){
            y = - y;
            x = 1 / x;
        }
        while(y > 0){
            if(y % 2 == 1) ans = ans * x;  // 快速幂次的方法
            x = x * x;
            y /= 2;
        }
        return ans;
    }
};
// 时间复杂度:O(log n)每次 y /= 2，意味着它的位数在每次循环中都减少一半; 空间复杂度:o(1)
    0 赞同 0 条回复
  • jaron 普通 2024年12月8日 上午9:43 
    class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        // 负数比正数多一个
        long y = n;
        if (y < 0) {
            // 负数次幂
            x = 1 / x;
            y = -y;
        }
        while (y > 0) {
            if (y % 2 == 1) {
                res *= x;
            }
            x *= x;
            y /= 2;
        }
        return res;
    }
}
    0 赞同 0 条回复
  • 迢迢星野 普通 2024年12月7日 下午8:50 
    class Solution {
    public double myPow(double x, int n) {
        // 如果 n 为负数，转换为正数，且 x 转换为且倒数 1/x；当 n == Integer.MIN_VALUE 时，-n 会越界，所以将 n 先转换为 long 类型
        long b = n;
        double res = 1.0;
        if (b < 0) {
            b = -b;
            x = 1 / x;
        }

        double tmp = x;
        // 将 b 转换为二进制，每遇到 1 时，就进行乘法计算
        while (b != 0) {
            if ((b & 1) == 1) {
                res *= tmp;
            }
            tmp *= tmp;
            b = b >> 1;
        }
        return res;
    }
}

    思路：位运算，注意 n 的取值范围。
    时间复杂度：O(logn)
    空间复杂度：O(1)

    0 赞同 0 条回复

# 回答此问题

后才能回答