C++--数值的整数次方

数值的整数次方

题目：
给定一个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
  
3
  
4
  
5
  
6
 

方法二：（严谨）

/**
 * 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); }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

思路：
这个方法利用了快速幂算法

快速幂算法验证：

#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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

总结：
假设我们需要计算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)  )

  

 

  
1
  
2
 

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/102224391