给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
把情况考虑完整：
2
−
5
2^{-5}
2−5,
2
0
2^0
20,
2
5
2^{5}
25
同时，直接进行相乘，也能计算出来，此时未考虑优化问题。
判断double是否相同的方法：equal
const double min_value = 1e-7;
bool equal(double num1, double num2)
{
if(num1 - num2 < - min_value || num1 - num2 > min_value)
{
return false;
}
else
{
return true;
}
}
equal的另一种实现方法：
int equal(double left, double right)
{
if((left - right) < min_value && (left - right) > -min_value)
return true;
else
return false;
}
只有在下面两个范围内，超过了浮点数表示精度，才认为两个相等，所以这里是 && 符号(易错)。
将最常见的几种情况考虑完整，依次相乘，可得出下面代码。
double Power(double base, int exponent)
{
if (equal(base, 0.0) && exponent <= 0)
return 0; //这里已经输入不合法了
bool flag_positive = true;
if (exponent < 0)
{
flag_positive = false;
exponent = -exponent;
}
else if (exponent == 0)
{
return 1;
}
double ret = 1.0;
for (size_t i = 0; i < exponent; i++)
{
ret *= base;
}
if (!flag_positive)
ret = 1.0 / ret;
return ret;
}
上述代码，思路比较直观，但仔细分析会发现，中间有可以优化的地方。
如果指数为32，我们在循环中做31次乘法。换个角度，我们知道了16次方，直接在16次方的基础上平方就可以获知到32次方的值。而16是8次方的值，以此类推，求32次方，只需要做5次乘法：先平方，平方的基础上求得4次方，4次方的基础上求得8次方，8的基础上求得16，16的基础上求得32.
其实上述思路就是 【快速求幂算法】，算法思路可以参考原文，算法伪代码为：
POWER_INTEGER(x, n)
1 pow ← 1
2 while (n > 0)
3 do if (n mod 2 = 1)
4 then pow ← pow * x
5 x ← x * x
6 n ← n / 2
7 return pow
实现代码见完整代码中Power_quick 部分。
注意：
if (exponent & 0x1)语句理解错误，需要注意。if (exponent & 0x1 == 1)，其中 ==的优先级更高，然后才是 &
#include <iostream>
#include <cstdlib>
#include <ctime>
const double Min_value = 1.0e-7;
class Solution
{
bool equal(double num1, double num2)
{
if (num1 - num2 < -Min_value || num1 - num2 > Min_value)
{
return false;
}
else
{
return true;
}
}
public:
//快幂法
double Power_quick(double base, int exponent)
{
if (equal(base, 0.0) && exponent <= 0)
return 0;
bool flag_positive = true;
if (exponent < 0)
{
flag_positive = false;
exponent = -exponent;
}
else if (exponent == 0)
{
return 1;
}
double ret = 1.0;
int tmp = exponent;
while (exponent > 0)
{
//如果是奇数，需要再继续乘 base，下面类似于取余(%)操作行，需要放在外面
if (exponent & 0x1) //n & 1 等价于 (n % 2) == 1
{
ret *= base;
// printf("1.ret: %d, exponent = %d, base = %.2lf\n", exponent & 0x1, exponent, base);
}
base *= base;
exponent >>= 1; n >>= 1 等价于 n /= 2
}
if (!flag_positive)
ret = 1.0 / ret;
return ret;
}
//依次乘
double Power_order(double base, int exponent)
{
if (equal(base, 0.0) && exponent <= 0)
return 0;
bool flag_positive = true;
if (exponent < 0)
{
flag_positive = false;
exponent = -exponent;
}
else if (exponent == 0)
{
return 1;
}
double ret = 1.0;
for (size_t i = 0; i < exponent; i++)
{
ret *= base;
}
if (!flag_positive)
ret = 1.0 / ret;
return ret;
}
};
int main()
{
Solution ans;
int start_time = clock();
double ret = ans.Power_quick(5, 10);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
start_time = clock();
ret = ans.Power_quick(5, 11);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
start_time = clock();
ret = ans.Power_order(5, 10);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
start_time = clock();
ret = ans.Power_order(5, 11);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
///
start_time = clock();
ret = ans.Power_quick(5, 30);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
start_time = clock();
ret = ans.Power_quick(5, 31);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
start_time = clock();
ret = ans.Power_order(5, 30);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
start_time = clock();
ret = ans.Power_order(5, 31);
printf("value: %.2lf, time: %lu\n", ret, clock() - start_time);
}
测试了一下时间，上面几个时间差不多，暂不知道是什么原因。
