欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指刷题日记-剑指 Offer 16. 数值的整数次方

程序员文章站 2022-03-12 22:25:45
题目描述题目链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/解题思路快速幂class Solution {public: double myPow(double x, int n) { // n 要转换为long, 因为int型会溢出 // runtime error: negation of -2147483648 cannot // be r...

题目描述

题目链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
剑指刷题日记-剑指 Offer 16. 数值的整数次方

解题思路

快速幂
剑指刷题日记-剑指 Offer 16. 数值的整数次方

class Solution {
public:
    double myPow(double x, int n) {
        // n 要转换为long, 因为int型会溢出
        // runtime error: negation of -2147483648 cannot 
        // be represented in type 'int';
        double res = 1;
        long num = n;
        if(num<0)
        {
            x = 1/x;
            num = -num;
        }
        while(num)         // 为零时表示不含有“1”
        {
            if(num&1) 
                res *= x;  // 当前权位为1就累乘
            x *= x;        // 平方
            num=num>>1;    // 右移,高位补零
        }

        return res;
    }
};

我的猜想:为什么指数n一定得按二进制展开?————因为指数展开成了二进制,根据指数运算的性质,所以x可以通过不断平方来得到相应位对应的权值。同时,按位与运算&和右移操作>>都是二进制运算,十分方便。

本文地址:https://blog.csdn.net/qq_42133142/article/details/112006867