【位运算专题】剑指 Offer 16. 数值的整数次方-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年4月19日下午11:12

// 时间复杂度为 logn
class Solution {
    public double myPow(double x, int n) {
        if(x == 1.0 || n == 0){
            return 1.0;
        }
        // 需要将 n转成long格式的N 当n=-2147483648时，-n超出了n的范围
        long N = n;
        return n < 0 ? 1.0 / quickMul(x,-N): 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 == 1 ? y * y * x : y * y ;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年1月15日下午6:07

1、需要注意n可以为负数，-2^31 <= n <= 2^31-1，所以n = -n需要用long，否则会溢出
2、将n转化为2进制
遍历范围：(; n!=0;n>>=1)；
当bit上为1时，res = res * x ，此时x是当前bit位对应x的次方
每右移一位，x = x * x，
3、主要使用x^n = x^a + x^b (a+b = n)

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

        }

    double res = 1;
    while(t>0) {
        if ((t&1) != 0) {
            res = res * x;
        }
        x=x * x;
        t = t>>1;
    }

    return res;
}
}

0 赞同 0 条回复

宁永久会员 2023年1月14日下午5:37

位运算的思想

class Solution {
    public double myPow(double x, int n) {
        long y = n;//int :-2147483648~2147483647否则取相反数会保存不下
        double sum = 1;
        if(y < 0){
            y = -y;
            x = 1 / x;
        }
        while(y != 0){
            if(y % 2 == 1){
                sum = sum * x;
            }
            y = y / 2;
            x *= x;
        }
        return sum;

    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月10日上午11:36

def myPow(x,n):
    res = 1

    if n < 0:
        n = -n
        x = 1 / x

    while n > 0:
        # 这里也可以用n % 2 == 1
        if n & 1 == 1:
            res = res * x
        x = x * x
        # 向右移动一位
        n = n >> 1
    return res

0 赞同 0 条回复

lucca 普通 2023年1月9日上午9:57

快速幂

坑：要用long存n，否则 -2147483648 转正数会溢出，因为 int 范围是 -2147483648 ~ 2147483647

class Solution {
    public double myPow(double x, int n) {
        boolean ne = false;
        long N = n;
        if (n < 0) {
            ne = true;
            N = -N;
        }

        double ans = 1, t = x;
        while (N > 0) {
            if ((N & 1) == 1) ans *= t;
            t = t * t;
            N >>= 1;
        }
        return ne ? 1.0 / ans : ans;
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月2日下午3:44

func myPow(x float64, n int) float64 {
    if n >= 0 {
        return quickMul(x, n)
    }
    return 1.0 / quickMul(x, -n) //若n < 0,按照n>0计算，取个倒数就可以了
}

func quickMul(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    y := quickMul(x, n/2) // 下一层     向下取整
    //当前层
    if n%2 == 0 {
        return y * y //若n能被2整除
    }
    return y * y * x //若n不能被2整除 
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午12:18

class Solution {
public: //分治
    double quikmul(double x, long long n){
        if(n==0) return 1.0;
        double y = quikmul(x,n/2);
        return n%2==0?y*y:y*y*x;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N>0?quikmul(x,N):1.0/quikmul(x,N);
    }
};

0 赞同 0 条回复

刺猬普通 2022年11月24日上午12:54

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

时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

xye 普通 2022年11月23日下午4:53

func myPow(x float64, n int) float64 {
    var sum float64
    sum = 1
    if n < 0 {
        n = - n
        x = 1 / x
    }
    tmp := x
    for n != 0 {
        if n & 1 == 1 {
            sum = sum * tmp
        }
        tmp = tmp * tmp
        n = n >> 1
    }
    return sum
}

时间O(logn) 空间O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月20日下午9:32

时间复杂度：O(logn)
空间复杂度：O(1)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 位运算
        def QuickMul(n):
            ans = 1.0
            x_contribute = x
            while n > 0:
                # 若最低位为1，结果就乘x
                if n % 2 == 1:
                    ans *= x_contribute
                # 每进一位都做平方
                x_contribute *= x_contribute
                # 舍弃n对应二进制数的最低位
                n //= 2
            return ans
        return QuickMul(n) if n >= 0 else 1.0 / QuickMul(-n)

0 赞同 0 条回复

鸿渐普通 2022年11月15日下午9:15

 double res = 1;
        long y = n;

        if (n < 0){
            //把负整数的指数幂转化成分数的正整数指数幂
            x=1/x;
            y=-y;
        }

        //如果指数是正数的话
        while (y > 0) {
            if (y % 2 == 1) {
                //如果右移之后是奇数的话还是在执行这个操作
                res = res * x;
            }
            x=x*x; //循环每次都计算这个 但是如果是偶数的话这个的值不会被加上

            //右移一位
            y=y/2;
        }

        return res;

0 赞同 0 条回复

Tolkien 永久会员 2022年11月15日下午9:13

public double myPow(double x, int n) {
        long N = n;
        return N < 0 ? 1.0 / quickMul2(x, -N) : quickMul2(x, N);
    }

    /**
     * 方法一：递归实现快速幂
     * 时间复杂度：O(logn)
     * 空间复杂度：O(logn)
     */
    public double quickMul(double x, long n) {
        // 递归结束条件
        if (n == 0) {
            return 1;
        }

        // 等价关系式
        // x^7 = (x^3)^2+1, x^6 = (x^3)^2
        double result = quickMul(x, n/2);
        return n % 2 == 0 ? result*result : result*result*x;
    }

    /**
     * 方法二：位运算实现快速幂
     * 时间复杂度：O(logn)
     * 空间复杂度：O(logn)
     */
    public double quickMul2(double x, long n) {
        // 2^13 = (2^8)*(2^4)*(2*1) 1101 = 1000 + 0100 + 0001
        // 可以发现，x^n次方可以拆分成x^a*x^b*x^c, a,b,c分别为幂的二进制形式中值为1的位所代表的十进制值
        // 因此，我们的思路是，遍历二进制数字，若为1，则乘以当前的幂指数

        double result = 1.0;

        // 通过右移位，从左往右遍历x的二进制，若位为1，则结果乘以当前的幂指数
        while (n > 0) {
            if (n % 2 == 1) {
                result = result * x;
            }
            // 右移1位，使倒数第二位成为最后一位，以实现遍历
            n = n >> 1;
            // 当前的幂指数
            x = x * x;
        }

        return result;
    }

0 赞同 0 条回复

小肸永久会员 2022年11月15日下午5:31

实现方式一：递归求一个数的指数。递归中用一个double型变量存储x的n/2次方结果，才是递归了logN次。时间复杂度O(logN)，空间复杂度O(logN)。

class Solution {
    public double myPow(double x, int n) {
        return n < 0 ? 1 / getPositiveExponent(x, -n) : getPositiveExponent(x, n);
    }
    private double getPositiveExponent(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double temp = getPositiveExponent(x, n / 2);
        return n % 2 == 0 ? temp * temp : temp * temp * x;
    }
}

实现方式二：迭代+快速幂。时间复杂度O(logN)，空间复杂度O(1)。

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

0 赞同 0 条回复

Whatever 永久会员 2022年11月14日下午8:55

时间O(logn)，空间O(1)

class Solution {
    public double myPow(double x, int n) {
        if(n == 0){
            return 1;
        }
        if(n == Integer.MIN_VALUE){
            return myPow(1/x, -(n+1)) * (1/x);
        }
        if(n < 0){
            return myPow(1/x, -n);
        }
        if(n % 2 == 1){
            return x * myPow(x,n-1);
        }else{
            double temp = myPow(x,n/2);
            return temp*temp;
        }
    }
}

0 赞同 0 条回复

y 普通 2022年11月14日下午8:42

var myPow = function(x, n) {
   if(n === 0) {
       return 1;
   } 
   if(n === 1) {
       return x;
   }

   let result = 1;
    //判断奇偶数
    //根据最右位是否为1来判断
   let absn = Math.abs(n);

   while(absn) {
       if(absn & 1) {
           result = result * x;
       } 
       x = x * x;
       absn = Math.floor(absn/2);
   }
   return n < 0 ? 1/result : result;
};

0 赞同 0 条回复

Y7n05h 普通 2022年11月14日下午5:17

class Solution {
public:
    double quicPower(double x, uint64_t n) {
        double res = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                res *= x;
            }
            x = x * x;
            n /= 2;
        }
        return res;
    }
    double myPow(double x, int n) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        return n > 0 ? quicPower(x, n) : 1.0 / quicPower(x, -(int64_t) (n));
    }
};

时间复杂度：O(lgN)

0 赞同 0 条回复

@ 普通 2022年11月14日上午10:32

/**
 * 假设: x = 2, n = 9
 * 9 = 1001(B) = 1*1 + 0*2 + 0*4 + 1*8
 * 2^9 = 2^(1*1) + 2^(0*2) + 2^(0*4) +2 ^(1*8)
 *
 * 时间复杂度 O(log2n)
 * 空间复杂度 O(1)
*/
class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long t = n;
        double res = 1.0;
        if(t < 0) {
            x = 1 / x;
            t = -t;
        }
        while(t > 0) {
            if((t & 1) == 1) res *= x;
            x *= x;
            t >>= 1;
        }
        return res;
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年11月12日上午10:42

public double myPow(double x, int n) {
        //时间复杂度O(lgn)
        //空间复杂度O(lgn)
        //快速幂运算
        long N = n;
        return N > 0 ? quickRow(x, N) : 1.0 / quickRow(x, -N);

    }

    private double quickRow(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickRow(x, N / 2);
        return (N & 1) == 1 ? y * y * x : y * y;
    }

0 赞同 0 条回复

庄重普通 2022年11月11日上午10:28

// 思路：
//     1.利用二进制计算x的n次幂，而且可直接减少幂运算的次数
//     2.eg：x的13次幂 13 —> 1    1     0     1    从13次减少到3次
//                          x^8  x^4   x^2   x^0
class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        long y = n;
        //二进制最高位0代表正数，1代表负数，int的范围为-2147483648——2147483647，2147483648不在int范围中，超出索引范围需要使用long类型进行保存
        //对负数处理为正数
        if(n < 0){
            y = -y;
            x = 1 / x;
        }

        while(y > 0){
            if(y % 2 == 1)
                res = res * x;

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

        return res;
    }
};
//时间复杂度O(logn)
//空间复杂度O(1)

0 赞同 0 条回复

天然普通 2022年11月10日下午10:38

先不管n的正负，都变成正的，然后进行计算，输出时判断n的正负，返回sum或1/sum

class Solution:
    def myPow(self, x: float, n: int) -> float:
        tem = x 
        absn= abs(n)
        sum=1
        while absn:
            if absn&1==1:sum *=tem 
            tem *=tem
            absn = absn>>1

        return sum if n>0 else 1/sum

0 赞同 0 条回复

派大星普通 2022年11月10日下午10:36

class Solution {
//时间复杂度O(logn)
//空间复杂度O(1)
    public double myPow(double x, int n) {
        long n1 = n;
        double sum = 1;
        //把整数的负数幂转换为分数的正整数幂
        if(n < 0) {
            n1 = -n1;
            x = 1 / x;
        }
        while(n1 > 0){
            if((n1 & 1) == 1)sum = sum * x;
            x = x * x;
            n1 = n1 / 2;                    
        }
        return sum;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月10日下午4:49

处理负数的情况

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){
            if (y%2==1){

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

0 赞同 0 条回复

易水寒永久会员 2022年11月10日下午2:28

快速幂

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

0 赞同 0 条回复

lobort 普通 2022年11月9日下午10:14

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

0 赞同 0 条回复

是梦终空永久会员 2022年11月9日下午6:56

本来还在疑惑为什么视频中要用y来代替n,试了一下才发现n是int 的
时间O(logn)
空间O(1)

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

0 赞同 0 条回复

T 普通 2022年11月9日下午6:02

class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long m = n;
        double res = 1.0;
        // 如果为负数，需要处理一下
        if(m < 0) {
            x = 1 / x;
            m = -m;
        }
        while(m > 0) {
            if((m & 1) == 1) {
                res *= x;
            }
            x *= x;
            m >>= 1;
        }
        return res;
    }
}

0 赞同 0 条回复

just 普通 2022年11月9日下午2:28

//快速幂，递归和迭代recursion和iteration
class Solution {
public:
double quickmul(double x,long long n){
double res=1.0;
double mul=x;
while(n>0){
if(n&1){
res=mul;
}
mul=mul;
n/=2;
}
return res;
}
double myPow(double x, int n){
long long k=n;
return n>=0? quickmul(x,k):1.0/quickmul(x,-k);

};

0 赞同 0 条回复

So 普通 2022年11月9日上午10:20

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;
            y /= 2;
        }
        return res;
    }
}

时间：O(log(n))，空间：O(1)

0 赞同 0 条回复

追普通 2022年11月9日上午10:10

class Solution {
public:
    double quickMul(double x, long long N) {
        if (N == 0) return 1.0;
        if (N == 1) return x;
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

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

快速幂 + 迭代时间复杂度O（logn）,空间复杂度O（1）
对于快排幂的递归还是有点不是很清楚，需要后面再花时间研究

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月8日下午11:41

快速幂 + 迭代

主要问题：用例中n给的超出int的范围，必须转换为long，不然表示的数有差异

时间复杂度O(logn) 即对n进行二进制拆分的复杂度

空间复杂度O(1)

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? getPow(x,N) : 1.0 / getPow(x,-N);
    }
    double getPow(double x,long N){
        double sum = 1;
        double tmp = x;
        while(N != 0){
            if((N & 1) == 1){
                sum *= tmp;
            }
            tmp *= tmp;
            N >>= 1;
        }
        return sum;
    }
}

快速幂 + 递归

每次递归都会使得指数减少一半，因此递归层数为O(logn)

时间/空间复杂度为O(logn)

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? getPow(x,N) : 1.0 / getPow(x,-N);
    }
    double getPow(double x,long N){
       if(N == 0) return 1.0;//0次方为1
       double y = getPow(x,N / 2);
       return N % 2 == 0 ? y * y : y * y * x;//如果为偶数次方则只需要y*y，如果为奇数次方则还需乘一个x
    }
}

0 赞同 0 条回复

青木普通 2022年11月8日下午11:07

/**
    位运算 没做出来，总算明白为啥是temp自乘
    时间复杂度O(logn)
    空间复杂度O(1)
 */

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

    public double multi(double x, long n){
        double ans = 1.0;
        double temp = x;
        while(n != 0){
            if((n & 1) == 1){
                ans *= temp;
            }
            temp *= temp;
            n = n >> 1;
        }
        return ans;
    }
}

/**
    不会...
    快速幂 递归写法
    时间复杂度O(logn)
    空间复杂度O(logn)
 */

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

    public double multi(double x, long n){
        if(n == 0) return 1.0;
        double y = multi(x, n/2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

0 赞同 0 条回复

Error 普通 2022年11月8日下午10:50

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        if n < 0:
            x, n = 1/x, -n
        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>=1
        return res

时间复杂度 O(log 2n)

0 赞同 0 条回复

黎昕普通 2022年11月8日下午10:42

这道题本质上是快速幂算法，快速幂最开始是按照递归方式做的，递归方式很简单，非递归稍微难理解一点，因为需要判断奇偶性，所以引入了位运算
时间复杂度 O(logn)
空间复杂度 O(1)
题目本身而言，还需要注意有负数指数

class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 快速幂的非递归方式，需要注意这道题还有负指数的情况
        flag=0
        if n<0:
            flag=1
            n=-1*n
        ans=1
        while n!=0:
            if n&1==1:
                ans*=x
            x*=x
            n=n>>1
        if flag==1:
            ans=1/ans
        return ans

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月8日下午10:10

时间复杂度为O（lgn）,空间复杂度为O（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;
    }
}

0 赞同 0 条回复

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

共以下 34 个回答

快速幂

# 回答此问题取消回复

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

共以下 34 个回答

快速幂

# 回答此问题 取消回复

# 回答此问题取消回复