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

=.= 普通 2024年4月4日下午9:22

class Solution {
public double myPow(double x, int a) {
double ans = 1;
long n = a;
n = Math.abs(n);

    while(n != 0){
        if((n & 1) == 1){
            ans *= x;
        }
        x *= x;
        n = n >> 1;
    }

    return a >= 0 ? ans : 1/ans;
}

}

long型

0 赞同 0 条回复

NULL 普通 2024年3月26日上午12:46

class Solution {
public double myPow(double x, int n) {
double res = 1;
long y = n;
// 如果 n 为负数，将 x 变为其倒数，n 变为正数
if (n < 0) {
y = -y;
x = 1 / x;
}
// 快速幂算法，将 x 的 n 次方分解为若干个平方的乘积
while (y > 0) {
// 如果当前 n 为奇数，将结果乘以 x
if (y % 2 1) {
res *= x;
}
// 将 x 变为其平方
x *= x;
// 将 n 减半
y /= 2;
}
// 返回计算结果
return res;
}
}

0 赞同 0 条回复

南梁陈庆之普通 2024年3月23日上午11:44

时间复杂度 O(log⁡n) 二分的时间复杂度为对数级别。
空间复杂度 O(1) 常数大小额外空间。

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

        return res;
    }
}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月22日下午5:28

class Solution {
    public double myPow(double x, int n) {

        double sum=1; //注意类型
        long y=n;

        if(n<0){
            y=-y;
            x=1/x;

        }

        double temp=x; //注意temp值要在x发生变化后定义

        while(y>0){
            if(y%2 == 1){
                sum*=temp;

            }
            temp*=temp;
            y=y>>1;

        }

        return sum;
    }
}

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月21日下午7:25

public double myPow(double x, int n) {
if(x0.0f) return 0.0d;
double res=1.0;
long b=n;
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 条回复

一个达不刘普通 2024年3月21日下午2:31

class Solution {
public:
double myPow(double x, int n) {

    //左移一位，一次幂运算

    if(!n) return  1;
    if(abs(n) == 1 ) return n>=0? x:1/x;//若n位负数，则倒换x。x的负数次方==1/x的的正数次方
    double a = myPow(x, n>>1);
    return n%2? a*a*x : a*a;

}

};

0 赞同 0 条回复

kfaebot 普通 2024年3月20日下午4:47

class Solution {
public:
    double myPow(double x, int n) {
        double result=1.0;
        double tmp=x;
        long nn=n;

        //n为负数时
        if(nn<0){
            tmp=1.0/tmp;
            nn=-nn;
        }

        while(nn){
            if((nn&1)==1){
                result*=tmp;
            }
            tmp*=tmp;
            nn=nn>>1;
        }
        return result;
    }
};

0 赞同 0 条回复

神经蛙普通 2024年3月20日上午12:04

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

0 赞同 0 条回复

方铎码农普通 2024年3月19日下午11:12

// 快速幂算法，x^n = x^(n/2) * x^(n/2)
// 向下整除 n//2等价于 右移一位 n>>1 ；
// 取余数 nmod  2等价于 判断二进制最右位 n&1

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

分治方法，时间复杂度O(logn)，空间复杂度O(1)

0 赞同 0 条回复

Jimmy 普通 2024年3月19日下午10:25

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

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

0 赞同 0 条回复

heathhou 普通 2024年3月19日下午8:44

class Solution {
public:
    double myPow(double x, int n) {
        double res = 1;
        // 试了下,使用uint也行
        long y = n;
        if( n < 0){
            y = -y;
            x = 1 / x;
        }
        while(y > 0){
            // 判断 y最有一位是否为1
            if(y & 1 == 1){
                res = res * x;
            }
            x *= x;
            // y右移1位
            y = y >> 1;
        }


        return res;
    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月19日上午8:08

打卡

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

0 赞同 0 条回复

Yox 普通 2024年3月19日上午2:40

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

0 赞同 0 条回复

云无深雁影普通 2024年3月19日上午12:51

class Solution {
public double myPow(double x, int n) {
if(x0.0f) return 0;
long b = n;
if(b < 0){
x = 1 / x;
b = – b;
}
double ans = 1;
double temp = x;
while(b!=0){
if((b & 1) 1){
ans *= temp;
}
temp *= temp;
b = b >> 1;
}
return ans;
}
}
//时间复杂度：O(logn)
//空间复杂度：O(1)

0 赞同 0 条回复

言之命至普通 2024年3月18日下午11:46

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        long y = n; //如果是int的话可能会溢出
        if(n < 0){ //如果n<0，就转一下做
            y = -y;
            x = 1 / x;
        }
        while(y > 0){
            if(y % 2 == 1){ //说明最后一位是1，需要让res乘以这一位的权重
                res = res * x;
            }

            x = x * x;
            y = y / 2; //丢掉最后一位
        }
        return res;
    }
}

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

0 赞同 0 条回复

MARS 普通 2024年3月18日下午11:38

day16第二题

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
    let res = 1
    let y = x, m = n
    if (n < 0) {  //若幂次小于0，变为正数
        m = -n
        y = 1 / x
    }

    while (m > 0) {   //当幂次大于0  
        if (m % 2 === 1) {  //如果是奇数，
            res = res * y
        }
        y = y * y
        m = Math.floor(m / 2)
    }
    return res
};

0 赞同 0 条回复

王位詮釋普通 2024年3月18日下午10:01

class Solution {
    public double myPow(double x, int n) {
        double result = 1;
        long y = n;//如果是int的话可能会溢出
        if(n<0){
            y = -y;
            x = 1/x;
        }
        while(y>0){
            if((y&1)==1){//说明最后一位是1，需要让result乘以这一位的权重
                result = result*x;
            }
            y = y >> 1;
            x = x*x;
        }
        return result;
    }
}
思路：m的n次方，其中n可以改为2的幂的和，比如3^(8+4+1)=3^8*3^4*3^1，也就是说让每一个权重进行相乘就行，而权重可以对n（13）进行向右移动获取。

0 赞同 0 条回复

紫芝普通 2024年3月18日下午9:34

思路：参考位运算

“`c++
class Solution {
public:
double myPow(double x, int n) {
long long N = n;
if (n < 0) { N = -N; } double temp = x; double ans = 1; while (N != 0) { if (N & 1 == 1) { ans = ans * temp; } temp *= temp; N >>= 1;
}
return n < 0 ? 1/ans : ans; } }; ```

0 赞同 0 条回复

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

共以下 18 个回答

# 回答此问题取消回复

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

共以下 18 个回答

# 回答此问题 取消回复

# 回答此问题取消回复