C++--数值的整数次方
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
数值的整数次方
题目：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
方法一（利用pow()函数，居然编译通过了？）：
class Solution {
public:
double Power(double base, int exponent) {
return pow(base,exponent);
}
};方法二：（严谨）
/**
* 1.全面考察指数的正负、底数是否为零等情况。
* 2.写出指数的二进制表达，例如13表达为二进制1101。
* 3.举例:10^1101 = 10^0001*10^0100*10^1000。
* 4.通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果。
*/
public double Power(double base, int n) {
double res = 1,curr = base;
int exponent;
if(n>0){
exponent = n;
}else if(n<0){
if(base==0)
throw new RuntimeException("分母不能为0");
exponent = -n;
}else{// n==0
return 1;// 0的0次方
}
while(exponent!=0){
if((exponent&1)==1)
res*=curr;
curr*=curr;// 翻倍
exponent>>=1;// 右移一位
}
return n>=0?res:(1/res);
}
思路：
这个方法利用了快速幂算法
快速幂算法验证：
#include<iostream>
#include<math.h>
#include<time.h>
using namespace std;
double Power(double base, int exponent) {
int n=exponent;
double result=1;
if(n<0)
n=-n;
while(n!=0)
{
if((n&1)==1)
result=result*base;
base*=base;
n>>=1;
}
return exponent<0?(1/result):result;
}
int main()
{
cout<<Power(2,10);
return 0;
}
总结：
假设我们需要计算3^10
快速幂算法最终就是需要计算 6561*9 实质就是 3的8次方再乘以3的二次方
感觉没有什么规律 我们把10写出2进制 1010
发现没有
第一个1就是我们需要乘的8 第二个1就是我们需要乘的2
所以结论就是：
先把幂转换为二进制数，再分别计算每个1产生的结果，最后再乘即可
看下面例子即可
10^1101 = 10^0001*10^0100*10^1000
3^1010=3^1000*3^0010 ( 3^10=(3^8)*(3^2) )
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
