学步园

题目：就是求取一个数的n次方，不考虑溢出问题，这里用的一个时间复杂度较低的方法解决

<pre name="code" class="cpp">#include <iostream>
#include <bitset>
using namespace std;
double getvalue(int base,int element)
{
	//除0外，每一个数都可以用2的次方来表示，用2进制数来保存element，这样求取base的element次方时可以简化为求取base的平方、四次方等
	bitset<32> bite(element);
	if (bite.none())
	{
		return 1;
	}
	int numof1=bite.count();
	int sum[32]={0};
	int count=0;
	//当bite中i位置上数字为1时，用sum保存base的i+1次方的结果
	double basesum=0;
	for (int i=0;i<32&&count<numof1;++i)
	{
		if (i==0)
		{
			basesum=base;
		}
		else
		{
			basesum=base*base;
		}
		if (bite.at(i)==1)
		{
			++count;
			sum[i]=basesum;
		}
	}
	basesum=1;
	for (int i=0;i<32;++i)
	{
		if (bite.at(i))
		{
			basesum*=sum[i];
		}
	}
	return basesum;
}
//递归方法求取
double getvalueother(double base, unsigned int element)
{
	if(element == 0)
		return 1;
	if(element == 1)
		return base;
	//element为偶数时，求取base的element/2次方的平方就可以
	//element为奇数是，求取base的（element-1）/2次方的平方就可以
	double result = getvalueother(base, element >> 1);
	result *= result;
	if(element & 0x1 == 1)
		result *= base;

	return result;
}
int main()
{
	int base=3;
	int element=2;
	double sum=0;
	sum=getvalue(base,element);
	cout<<sum<<endl;
	sum=0;
	sum=getvalueother(base,element);
	cout<<sum<<endl;
	return 0;
}