数值整数次方

/********************************************
题目：实现函数double Power(double base, int exponent)
求base的exponent次方。不得使用库函数，同时不需要考虑
大数问题。
********************************************/


#include<iostream>

bool equal(double num1, double num2);
double powerWithUnsignedExponent(double base, unsigned int absExponent);
double Power(double base, int exponent)
{
	if(equal(base,0) && exponent <=0)	//考虑无效输入
		throw new std::exception("Invalid input!");

	unsigned int absExponent = exponent;
	if(exponent < 0)					//考虑指数为负数的情况
		absExponent = unsigned int(-exponent);
	
	double result = powerWithUnsignedExponent(base,absExponent);
	
	if(exponent<0)						//得到指数为负数的结果
		return 1.0/result;

	return result;
}
/*时间复杂度为O(N)
double powerWithUnsignedExponent(double base, unsigned int absExponent)
{
	double result = 1.0;
	for(int i=1; i<=absExponent; i++)	//实现base^absExponent
		result *= base;
	return result;
}
*/
//判断两个double是否相等
bool equal(double num1, double num2)	
{
	if((num1-num2>0.0000001)
		&& (num1-num2<0.0000001))
		return true;
	else
		return false;
}


//上面注释的powerWithUnsignedExponent()方法虽然能满足功能，
//但是不够高效时间复杂度为O(n)
//以下方法利用
//a^n = a^(n/2) * a^(n/2);当n为偶数
//a^n = a^((n-1)/2) * a^((n-1)/2) * a;当n为奇数
//其时间复杂度为O(NlogN)
double powerWithUnsignedExponent(double base, unsigned int absExponent)
{
	if(absExponent == 0)
		return 0;
	if(absExponent == 1)
		return base;
	double result = powerWithUnsignedExponent(base,absExponent >> 1);//右移代替除以2
	result *= result;
	if(absExponent & 0X01 == 1)		//判断absExponent是不是奇数
		result *= base;
	return result;
}

int main()
{
	double result1 = Power(2,4);	//基数和指数都为正式
	double result2 = Power(2,0);	//指数为0
	double result3 = Power(-2,1);	//指数为1
	double result4 = Power(-3,-2);	//指数为负数

	std::cout << result1 <<std::endl;//结果输出
	std::cout << result2 <<std::endl;
	std::cout << result3 <<std::endl;
	std::cout << result4 <<std::endl;
	return 0;	
}
//由于计算机表示的小数(float和double)都有误差，我们不能直接用等号(==)
//判断两个小数是否相等。如果两个小数的差的绝对值很小，比如小于0,.0000001
//就可以认为他们相等。
//用位运算替换乘除法，效率高很多

==参考剑指offer

数值整数次方,布布扣,bubuko.com

数值整数次方

原文：http://blog.csdn.net/walkerkalr/article/details/20611357