九号球普通 2023年11月20日下午8:58

“`java
考虑边界问题，int的最小值转成正数会超过最大值的范围，越界
class Solution {
public double myPow(double x, int n) {
double res = 1d;
if (x == 0) {
return x;
}
if (n == -Integer.MAX_VALUE – 1) {
x = 1/(x*x);
n = -(n/2);
}
if (n < 0) { x = 1/x; n = -n; } while (n != 0) { if ((n & 1) == 1) { res = res * x; } n = n >> 1;
x = x * x;
}
return res;
}
}

0 赞同 0 条回复

招舟子普通 2023年9月1日下午11:50

class Solution {
public double myPow(double x, int n) {
double sum=1;
long N = n;
if(n<0){
N = -N;
x = 1/x;
}
while(N>0){
if((N&1)1){
sum = sumx;
}
x = xx;
N=N>>1;
}
return sum;
}
}
嘎嘎

0 赞同 0 条回复

jhfuture 普通 2023年8月21日下午8:39

“`java
这里需要注意的就是需要进行类型的转换。n如果为负值
public double myPow(double x, int n) {

//当成二进制看待，如果例如n=13 1+4+8 1+4+8 1101 x 6
//2+4 110
double res=1;
long y=n;
if(y<0){
y=-y;
x=1/x;
}
while(y>0){
if(y%21){
res=resx;
}
x=xx;
y=y>>1;
}
return res;

0 赞同 0 条回复

彦，，# 普通 2023年8月3日下午4:56

//二分法
    double myPow(double x, int n) {
        if(0 == x) return 0;
        long b = n;
        double res = 1.0;
        if (0 > b) {
            x = 1/x ;
            b = -b;
        }
        while(b != 0){
            if((b&1) == 1){
                res *= x;
            }
            x *= x;
            b>>= 1;
        }
        return res;
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:52

“`C++
double myPow(double x, int n) {
if (n == 0) {
return 1.0;
}

double result = 1.0;
// 处理负指数的情况
long long absN = abs(static_cast<long long>(n));

// 快速幂算法
while (absN > 0) {
    if (absN % 2 == 1) {
        result *= x;
    }
    x *= x;
    absN /= 2;
}

return (n < 0) ? 1.0 / result : result;

}

“`

0 赞同 0 条回复

花老爷普通 2023年7月14日下午5:40

快速幂
时间：O(logn)
空间：O(1)

class Solution {
    public double myPow(double x, int n) {
        double ans = 1.0, base = x;
        long N = n; // 不可直接long N = n > 0 ? -n : n;
        N = n < 0 ? -N : N;
        while (N > 0) {
            if ((N & 1) == 1) {
                ans *= base;
            }
            base *= base;
            N = N >> 1;
        }
        return n > 0 ? ans : 1.0 / ans;
    }
}

0 赞同 0 条回复

憨憨永久会员 2023年7月14日上午10:48

每次取余然后计算

class Solution {
    public double myPow(double x, int n) {
        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 /= 2;
        }
        return res;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月13日下午10:44

【思路】利用位运算做优化，需要考虑n为正/负数两种情况
【复杂度】时间复杂度最好情况O(logn)最坏O(n)，空间复杂度O(1)

class Solution {
public:
    double myPow(double x, int n) {
        double result = 1;
        int tmp = x;
        unsigned int _n = std::abs(n);
        while(_n) {
            if (_n & 1) result *= x;
            x *= x;
            _n >>= 1;
        }
        return n >= 0? result: 1/result;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月13日下午3:21

class Solution {
    public double myPow(double x, int n) {
        long y = n; //必须先转为long再取反，否则最小负数的相反数没法表示
        if(n < 0) {
            return f(1/x, -y);
        } else {
            return f(x, y);
        }


    }

    public double f(double x, long n) {
        double sum = 1;
        while(n > 0) {
            if((n & 1) == 1) {
                sum *= x;
            }
            x *= x;
            n = n >>> 1;
        }
        return sum;
    }
}

时间复杂度o(logn), 空间复杂度o(1)

0 赞同 0 条回复

江畅普通 2023年7月12日下午8:20

// 数值的整数次方
// 时间复杂度 O(logN)
// 空间复杂度 O(1)
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) { return 1; }

        // myPow(1/x, -n), 避免 -n 整型溢出
        if (n == INT_MIN) { return myPow(1 / x, -(n + 1)) / x; }

        if (n < 0) { return myPow(1 / x, -n); }

        // 指数 n 为奇数
        // n % 2 == 1
        // n & 1 == 1
        if (n & 1 == 1) { return x * myPow(x, n - 1); }
        // 指数 n 为偶数
        else { 
            double sub = myPow(x, n >> 1);
            return sub * sub; 
        }
    }
};

0 赞同 0 条回复

屠龙手段普通 2023年7月11日下午7:35

快速幂运算，时间复杂度O(logn) 空间复杂度O(1)

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

0 赞同 0 条回复

橙子陈普通 2023年7月9日下午10:00

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;
    }
}

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

0 赞同 0 条回复

WhyNot 普通 2023年7月8日下午4:38

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

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

0 赞同 0 条回复

硬核洋葱普通 2023年7月7日下午9:49

class Solution {
public:
    double mylongPow(double x, long long n){
        double xproduct = x, ans = 1;

        while(n){
            if(n & 1)
                ans *= xproduct;
            n = n >> 1;
            xproduct *= xproduct;
        }
        return ans;
    }

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

将 n 以二进制位表示，如果第 k 位为1，则最终次方结果应乘上 x^(2^k)，因为是 int 类型的数，从补码角度来看如果从右往左第 32 位为 1，结果应乘上 x^(-2^32)
这样不行，因为会有 inf 的问题
把负数转换成正数计算，单独处理-2^31的问题，将其结果直接设置为 0
看题解，发现自己写得太麻烦了，干脆把 n 升级一个数据结构，用 long long 写，就没这个问题了
时间复杂度 O(logn) 空间复杂度O(1)

0 赞同 0 条回复

硬核洋葱普通 2023年7月7日下午9:49

class Solution {
public:
    double mylongPow(double x, long long n){
        double xproduct = x, ans = 1;

        while(n){
            if(n & 1)
                ans *= xproduct;
            n = n >> 1;
            xproduct *= xproduct;
        }
        return ans;
    }

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

将 n 以二进制位表示，如果第 k 位为1，则最终次方结果应乘上 x^(2^k)，因为是 int 类型的数，从补码角度来看如果从右往左第 32 位为 1，结果应乘上 x^(-2^32)
这样不行，因为会有 inf 的问题
把负数转换成正数计算，单独处理-2^31的问题，将其结果直接设置为 0
看题解，发现自己写得太麻烦了，干脆把 n 升级一个数据结构，用 long long 写，就没这个问题了
时间复杂度 O(logn) 空间复杂度O(1)

0 赞同 0 条回复

Dsjh 普通 2023年7月7日下午5:56

MY

快速幂

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

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月7日下午3:09

class Solution:
    def myPow(self, x: float, n: int) -> float:

        res = 1

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

        while n != 0:
            if n % 2 == 1:
                res *= x

            x *= x
            n = n // 2

        return res

时间复杂度：O(log(n))

0 赞同 0 条回复

Yodl. 普通 2023年7月7日下午1:51

//快速幂
//时间复杂度：O(logN) 空间复杂度：O(1)
class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        long y = n; // 不能用 int。
        if (n < 0) {
            y = -y;
            x = 1 / x;
        }
        while (y > 0) {
            if (y % 2 == 1) {
                res *= x;
            }

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

0 赞同 0 条回复

Vow the vow。普通 2023年7月7日下午12:00

看的解析写的。

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

0 赞同 0 条回复

行动派小彩笔普通 2023年7月7日上午12:16

// 时间复杂度O(logn) 空间复杂度O(1)
class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        double ans = 1;
        long y = n; //int类型会产生整型溢出的情况
        if(n<0)
        {
            y = -y;
            x = 1/x;
        }

        while(y)
        {
            if(y&1)
            {
                ans*=x;
            }
            x*=x;
            y>>=1;
        }

        return ans;
    }
};

0 赞同 0 条回复

yxy 普通 2023年7月6日下午11:55

时间复杂度O(logn)

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

0 赞同 0 条回复

Jerry 普通 2023年7月6日下午11:04

 // 位运算：分解+递归
class Solution {
    public double myPow(double x, int n) {
        if (n < 0) return myPow(1 / x, -n); //取倒数
        if (n == 0) return 1;
        if (n == Integer.MAX_VALUE) return myPow(1 / x, -(n + 1));
        if (n % 2 == 1) { // 奇数
            return x * myPow(x, n - 1); //递归
        }
        double sub = myPow(x, n / 2);
        return sub * sub;
    }
}

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

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月6日下午10:33

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

class Solution {
    public double myPow(double x, int n) {
        double sum = 1;
        long n_abs = n; // int类型范围 [-2147483648, 2147483647]。 如果负数为边界值，变成正数后会存不下
        if(n < 0){
            n_abs = -n_abs;  
            x = 1/x;
        }
        while(n_abs != 0){
            if((n_abs & 1) == 1){
                sum *= x;
            }
            n_abs = n_abs >> 1;
            x *= x;
        }
        return sum;
    }
}

0 赞同 0 条回复

小吕普通 2023年7月6日下午10:05

c++实现
double myPow(double x, int n) {
double sum = 1;
double temp = x;
long ln=n;
if(n<0)
{
ln = -ln;
temp = 1/temp;
}
while(ln!=0)
{

        if(ln&1==1)
        {
            sum*=temp;
        }
        temp *=temp;
        ln=ln>>1; 
    }
    return sum;
}

0 赞同 0 条回复

Ming 普通 2023年7月6日下午9:17

考虑n为负数时，将x = 1/x, n = -n;

public double myPow(double x, int n) {
        double sum = 1;
        long y = n;
        if(n < 0) {
            x = 1/x;
            y = -y;
        }
        while(y > 0) {
            if( (y & 1) == 1) {
                sum *= x;
            }
            x *= x; // 记录第几个1从右往左 个位 十位百位...
            y = y >> 1;
        }
        return sum;
    }

0 赞同 0 条回复

张开怀普通 2023年7月6日下午7:43

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

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

0 赞同 0 条回复

局外人普通 2023年7月6日下午7:40

思路：快速幂，二进制展开
时间复杂度：O(logn) 空间复杂度：O(1)

class Solution {
    public double myPow(double x, int n) {
        if(x==0)    return 0;

        long b = n;
        double res = 1.0;

        if(b<0){
            b = -b;
            x = 1/x;
        }

        while(b>0){
            if((b&1)==1)   res *= x;

            x *= x;
            b >>= 1;
        }

        return res;
    }
}

0 赞同 0 条回复

伏月三十普通 2023年7月6日下午6:40

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

时间logn 空间1

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月6日下午5:56

//思路：依次遍历n的每一个二进制位，根据每一位的权重做累加，注意n为负值
//时间O(logn)  空间O(1) 
public double myPow(double x, int n) {

        boolean negative = n < 0;   //是否为负数
        long k = (long)n;   //转为Long
        k = Math.abs(k);

        double weight = x;     //记录当前位权重
        double result = 1;

        while(k != 0){  
            //依次遍历每一个二进制位
            result = (k & 1) == 1 ? result * weight : result; 

            k = k >> 1; //遍历下一位
            weight = weight * weight;   //权重扩大
        }

        return negative ? 1/result : result;
    }

0 赞同 0 条回复

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

共以下 29 个回答

MY

# 回答此问题取消回复

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

共以下 29 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复