剑指刷题日记-剑指 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/
解题思路
快速幂
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