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

hi 普通 2023年8月16日下午10:09

快速幂处理，需要提前处理一下n 为负数的情况
n为负数时需要转变一下类型，用long类型存储，因为int类型的负数的最小值变为正数后int存不下

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

0 赞同 0 条回复

doordie. 普通 2023年8月15日上午11:36

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){
            // 如果二进制最右一位是1 则乘以x  依次判断b1、b2 ... bm
            if((b&1)== 1)   res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

0 赞同 0 条回复

艺普通 2023年8月3日下午11:07

“`c++
代码
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n == -1) return 1 / x;
return myPow(x * x, n >> 1) * myPow(x, n & 1);
}
};

0 赞同 0 条回复

普通 2023年8月1日下午10:49

c++ 位运算真的强
class Solution {
public:
double myPow(double x, int n) {
if (n 0) return 1;
if (n 1) return x;
if (n -1) return 1 / x;
double h = myPow(x, n >> 1);
double m = myPow(x, n & 1);
return h * h * m;
}
};

0 赞同 0 条回复

CaCO3 永久会员 2023年8月1日下午7:49

”’java
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ret = 0;
while(n != 0){
n &= n-1;//将二进制位中最低位的1变为0之后的结果
ret++;

    }
    return ret;
}

}
”’
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

北辰普通 2023年7月31日下午7:25

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

    //快速幂
    public static double quickMul(double x,long N) {
        double ans = 1.0;
        while(N>0) {
            if((N&1) == 1) {
                ans = ans*x;
            }
            x *= x;
            N>>=1;
        }
        return ans;
    }
}

0 赞同 0 条回复

Mby 普通 2023年7月29日下午9:41

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

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月27日下午11:29

class Solution {
    public double myPow(double x, int n) {
        // 普通方法会超时，要使用快速幂方法
        // 二分法的思想
        // 递归地求，把n不断二分
        // 负数是先求正数，再倒过来
        return n>=0?quickMul(x,n):1/quickMul(x,-n);

    }

    public double quickMul(double x, int n) {
        if(n==0) return 1;
        double res = quickMul(x,n/2);
        return n%2==0?res*res:res*res*x;
    }
}

时间复杂度：O（logn）

0 赞同 0 条回复

NullPointerException 普通 2023年7月27日上午11:55

class Solution {
public double myPow(double x, int n) {
if(n<0)
{
x=1/x;
n=-1n;
}
double result = 1;
//二进制思路 n变为2进制如 0101 用每一位2^位能表示回十进制
while(n!=0)
{
if((n&1)1)
{
result=x; //说明这一位可以计算
}
x=x;//不断乘积
n>>>=1;
}
return result;

}

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月26日下午9:19

代码

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 条回复

Marshan 普通 2023年7月26日下午7:08

快速幂的思想，思考时通过转换成2进制好理解

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 *= x;
            }
            x *= x;
            y >>= 1;
        }
        return res;
    }
};

0 赞同 0 条回复

CKX 普通 2023年7月26日下午4:38

func myPow(x float64, n int) float64 {
    res := 1.0
    y := int64(n)
    //负数
    if n < 0 {
        y = -y
        //倒数
        x = 1 / x
    }
    for y > 0 {
        if y % 2 == 1 {
            res *= x
        }
        x *= x
        y /= 2
    }
    return res
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月25日下午4:49

class Solution {

    public double myPow(double x, int n) {
        // 假设 2 的 -2 次方
        double res = 1.0;
        long b = n;
        if (b < 0) {
            x = 1/x;
            b = -b;
        }
        while (b > 0) {
            if ((b&1) == 1) {
               res = res * x;
            }
            // 每移动一位就成个x，相当于把1位置的权重*1 x是标记权重的 示例2的13次方 3的13次方
            x = x * x;
            b = b >> 1;
        }
        return res;
    }


}

0 赞同 0 条回复

人生何处不青山普通 2023年7月25日上午11:33

快速幂

function myPow(x: number, n: number): number {
    if (x === 0) return 0;
    if (n < 0) {
        x = 1 / x;
        n = -1 * n;
    }
    let res = 1;
    while(n) {
        if(n & 1) {
            res *= x;
        }
        n >>>= 1;
        x *= x;
    }
    return res;
};

0 赞同 0 条回复

刹那芳间普通 2023年7月25日上午11:10

class Solution {
    public double myPow(double x, int n) {
        long b = n;//INT_MIN的绝对值比INT_MAX大1，会保存不下
        double res = 1.0;
        if(b < 0){
            b = -b;
            x = 1/x;
        }
        while(b > 0){
            if((b&1) == 1){
                res = res * x;
            }
            x = x * x;
            b = b>>1;
        }
        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年7月25日上午12:00

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){
            // 最后一位为1，需要乘上该位上的权重
            if((b & 1) == 1){
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

0 赞同 0 条回复

#00456B 普通 2023年7月24日下午7:21

class Solution {
public:
    double myPow(double x, int n) {
        //快速幂的方法
        double ans = 1;
        //处理负数
        long y = n;//这里不能用int，因为INT_MIN的绝对值比INT_MAX大1，会保存不下
        if(y < 0){
            y = -y;
            x = 1/x;
        }
        while(y > 0){
            if(y & 1 == 1){// y % 2 == 1
                ans = ans * x;
            }
            x *= x;// x^1 x^2 x^4 x^8
            y = y >> 1;// y /= 2;
        }
        return ans;
    }
};

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月24日下午6:15

7.24
Day16：下面是代码

class Solution {
    public double myPow(double x, int n) {
        if(x == 0) return 0;
        //因为int类型 -231 <= n <= 231-1，那么n取最小负数，
        //再进行n = -n;时，正数2147483648就刚好超出了1
        long y = n;
        double sum = 1.0;
        if(y < 0){
            x = 1 / x;
            y = -y;
        }
        while(y > 0){
            if((y & 1) == 1){
                sum *= x;
            }
            x *= x;
            y >>= 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月24日下午5:34

快速幂

class Solution {
    public double myPow(double x, int n) {
        double res=1;
        long p=n;
        if(n<0){
            p=-p;
            x=1/x;
        }
        while(p>0){
            if(p%2==1){
                res=res*x;
            }
            x=x*x;
            p=p/2;//将二进制数向右移，去除最后一位
        }
        return res;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月24日下午4:02

快速幂

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

0 赞同 0 条回复

June 普通 2023年7月24日下午3:35

func myPow(x float64, n int) float64 {
    var sum float64 = 1
    var tmp float64 = x
    var flag bool = false
    if n < 0 {
        n = -n
        flag = true
    }
    for n != 0 {
        if n & 1 == 1 {
            sum *= tmp
        }
        tmp *= tmp
        n = n >> 1
    }
    if flag == true {
        sum = 1/sum // 负数幂
    }
    return sum
}

0 赞同 0 条回复

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

共以下 21 个回答

# 回答此问题取消回复

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

共以下 21 个回答

# 回答此问题 取消回复

# 回答此问题取消回复