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

题目描述

题目链接：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 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