(本博客旨在个人总结回顾)
题目描述:
实现函数double Power(double base, int exponent),求base的exponse次方。不得使用库函数,同时不需要考虑大数问题。
解题思路:
首先从数学的定义去分析该题:
①任何非0的0次方等于1.
②base^exponent当exponent为负数值有base^exponent=1.0/(base^(-exponent)) 此时base为0,exponent为负数为无效输入。
需要注意:
①判断base等于0时不能直接判断,float、double用计算机表示是有误差的。
解法一:
#include "stdafx.h"
#include <iostream>
using namespace std;
/*
* @name Equal
* @brief 判断两个浮点数是否相等
* @param [in] double lfValue1
* @param [in] double lfValue2
* @return bool
*/
bool Equal(double lfValue1, double lfValue2)
{
if (lfValue1 - lfValue2 > -0.0000001
&& lfValue1 - lfValue2 < 0.0000001)
{
return true;
}
return false;
}
/*
* @name PowerUnsignedExponent
* @brief 求base^exponent (exponent为正数)
* @param [in] double base
* @param [in] int exponent
* @return double
*/
double PowerUnsignedExponent(double base, int exponent)
{
double lfResult = 1.0;
while (exponent--)
{
lfResult *= base;
}
return lfResult;
}
bool g_bInvalidInput = false;
/*
* @name Power
* @brief 求base的exponent次方
* @param [in] double base
* @param [in] int exponent
* @return double
*/
double Power(double base, int exponent)
{
g_bInvalidInput = false;
if (Equal(base, 0.0) && exponent < 0)
{
g_bInvalidInput = true;
return 0.0;
}
if (Equal(base, 0.0))
{
return 0.0;
}
if (exponent == 0)
{
return 1.0;
}
double lfResult = 1.0;
bool bPositive = exponent >= 0 ? true : false;
if (!bPositive)
{
exponent = -exponent;
}
lfResult = PowerUnsignedExponent(base, exponent);
if (!bPositive)
{
lfResult = 1.0 / lfResult;
}
return lfResult;
}
int _tmain(int argc, _TCHAR* argv[])
{
//测试正常值 -2 和 2 的平方和立方
cout << "2^2=" << Power(2.0, 2) << endl;
cout <<"error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
cout << "-2^2=" << Power(-2.0, 2) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
cout << "2^3=" << Power(2.0, 3) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
cout << "-2^3=" << Power(-2.0, 3) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
//测试exponent为负值
cout << "2^-3=" << Power(2.0, -3) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
cout << "-2^3=" << Power(-2.0, -3) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
//测试exponent为负值
cout << "0^-3=" << Power(0, -3) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
cout << "-3^0=" << Power(-3.0, 0) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
//大数测试
cout << "2^32=" << Power(2.0, 32) << endl;
cout << "error:" << (g_bInvalidInput == false ? "no error" : "invalid") << endl;
system("pause");
return 0;
}
高效解法:
相关知识:
位运算效率高于(*)乘、(\)除、(%)取余
只需改变上面解法的PowerUnsignedExponent函数:
/*
* @name PowerUnsignedExponent
* @brief 求base^exponent (exponent为正数)
* @param [in] double base
* @param [in] int exponent
* @return double
*/
double PowerUnsignedExponent(double base, int exponent)
{
if (exponent == 1)
{
return base;
}
//右移一位代替除2操作
double lfResult = PowerUnsignedExponent(base, exponent >> 1);
lfResult *= lfResult;
//使用位与操作判断奇、偶
if (exponent & 1 == 1)
{
lfResult *= base;
}
return lfResult;
}
运行结果: