C++|幂运算:简单循环、优化后的递归或循环实现

对于手动幂运算，如求2^10，可以有直接和较简便的方法：

用计算机程序表示也是如此：

1 简单循环

unsigned power(unsigned x, unsigned n)
{
	if(n==0)
		return 1;
	unsigned sum = 1;
	for(int i=0; i<n; i++)
		sum *= x;
	return sum;
}

2 优化后的递归实现

unsigned pow(int x, int n)
{
	if(n==0)
		return 1;
	if(n==1)
		return x;
	else
	{
		int s = pow(x,n/2);
		if((n%2)==0)
			return s*s;
		else
			return s*s*x;
	}
}

过程图示：

3 优化后的循环实现（结合位运算）

unsigned pow2(int x, int n)
{
	int result;
	if(n==0)
		return 1;
	while((n&1)==0)
	{
		n>>=1;
		x *= x;
	}
	result = x;
	n>>=1;
	while(n!=0)
	{
		x *= x;
		if((n&1)!=0)
			result *=x;
		n>>=1;
	}
	return result;
}

过程图标：

－End－