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

Sheng 永久会员 2023年9月11日下午8:19

看的答案

class Solution {
        //数值的整数次方
    //实现pow(x,n)，即计算x的n次幂函数。不得使用库函数。n可能小于0
    //关键在于怎么分解n使计算简单快捷
    //x的13次方 = x^8 * x^4 * x^1
    //x的值为 x^1 x^2 x^3 x^4
    //13的二进制为1101，从右往左，有1的地方就乘对应的x的次方，否则跳过
    public double myPow(double x, int n) {
double res = 1;
        long y = n;//负数int最小值转为整数后溢出，因此需要long
        if(n < 0) {
            y = -y;
            x = 1 / x;
        }

        while(y > 0) {
            if(y % 2 == 1) {//从右往左，计算有1的地方
                res = res * x;//有1的地方就乘对应的x的次方，否则跳过
            }
            x = x * x;//x的值为 x^1 x^2 x^3 x^4...
            y = y / 2;//从右往左，计算有1的地方
        }
        return res;
    }
}

0 赞同 0 条回复

小肸永久会员 2023年9月6日上午10:52

lass Solution {
    public double myPow(double x, int n) {
        long N = n;//这里强转一下，防止n=Integer.MIN_VALUE，然后-n时溢出
        return n < 0 ? 1.0 / getPow(x, -N) : getPow(x, N);
    }
    // private double getPow(double x, long n) {
    //     if (n == 0) {
    //         return 1.0; 
    //     }
    //     if (n == 1) {
    //         return x;
    //     }
    //     double doubleX = getPow(x, n / 2L);
    //     return n % 2 == 0 ? doubleX * doubleX : doubleX * doubleX * x;
    // }
    private double getPow(double x, long n) {
        double tmp = x;
        double res = 1.0;
        //x^10 = x^1100 = x^1000 * x ^0100
        while (n > 0) {
            //直接判断低位是否为1，为1就累乘到res中
            if (n % 2 == 1) {
                res *= tmp;
            }
            tmp *= tmp;
            n /= 2;//移除最低位，相当于右移一位
        }
        return res;
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年9月6日上午8:45

//位运算中，n的m次方，其实也有模板

// 小数如何进行位运算？
class Solution {
public:
    // 此中n永远为正数的情况
    double quickMul(double x, long long n){
        double tmp = 1;
        double x_contribute = x;
        // 将n次方的次数n，二进制化，即可知道分别需要x的0次方，x的2次方，x的4次方等等都需要哪几个，每个各一个
        // 如果是13次，那么对应二进制为1101，则需要x的2^0次方1个，x的2^2次方1个，x的2^3次方1个
        // x * x^4 * x^8
        while(n > 0){ // 这个地方由于是有小数，于是取整时需要大于0，小数位运算和0的判别不清楚
            if((n&1) == 1){ // 需要将倍乘结果利用的时候
                tmp = tmp * x_contribute;
            }
            // 自身不断地倍乘，x的2次，4次，8次，···
            x_contribute = x_contribute * x_contribute;
            n = n>>1;
        }
        return tmp;
    }
    double myPow(double x, long long n) {
        // 正数次方和倒数次方
        if(n>=0){
            return quickMul(x, n);
        }else{
            return 1.0/quickMul(x, -n);
        }
    }
};

0 赞同 0 条回复

sincere 普通 2023年9月4日下午5:18

思路：从低位开始循环判断，如果位数是1结果res乘以x，不是则不操作，每次x都会乘以自己，N都会右移一位，这样每次x都是当前位对应的次方值。
复杂度：时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        if (n == 0) {
            return res;
        }
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        while (N > 0) {
            if ((N & 1) == 1) {// 最后一位是1
                res *= x;
            }
            x *= x;
            N >>= 1;// 右移一位
        }
        return res;
    }
}

0 赞同 0 条回复

c 普通 2023年8月31日下午7:30

快速幂递归

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 a = myPow(x,n/2);
        double b = myPow(x,n%2);
        return a*a*b;
    }
}

迭代

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) {
        double res = 1.0;
        double x_contribute = x;
        while (N > 0) {
            if (N % 2 == 1) {
                res *= x_contribute;
            }
            x_contribute *= x_contribute;
            N /= 2;
        }
        return res;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月29日下午11:57

1、测试用例301/304，（n=-2147483648报错）

class Solution {
    public double myPow(double x, int n) {
        if(n == 0){
            return 1.0;
        }
        if(x == 0 || x == 1){
            return x;
        }
        Boolean flag = false;
        if(n < 0){
            flag = true;
            n *= -1;
        }
        double res = x;
        for(int i=1; i<n; i++){
            res *= x;
        }
        if(flag){
            return 1.0/res;
        }
        return res;
    }
}

2、快速幂

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月29日下午8:53

//时间复杂度O(logn)
class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        long long y=n;
        if(n<0)
        {
            x=1/x;
            y=-y;
        }
        double ans = 1;
       while(y)
       {
           if(y&1) ans*=x;
           y>>=1;
           x*=x;
       }
        return ans;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月29日下午7:54

快速幂

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

0 赞同 0 条回复

JustRtn 普通 2023年8月29日下午3:35

快速幂
时间复杂度O(log N)，空间复杂度O(1)

class Solution {
public:
    double myPow(double x, int n) {
        double result { 1.0 };
        long power { n }; // 避免溢出

        if (n < 0) {
            x = 1/x;
            power = ~power + 1;
        }

        while (power > 0) {
            if (power & 1) {
                result *= x;
            }
            power >>= 1;
            x *= x;
        }

        return result;
    }
};

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复