题解 | #数值的整数次方#

快速幂。思路就是增大底数减少循环次数。下面用^表示指数运算，讨论a^b非负指数情况。

当b为偶数时，a^b=(a^2)^(b/2)

当b为奇数时，a^b=a(a^2)^(b/2)

程序实现时，奇偶判断可以用位与运算，除2可以用位移运算，负指数转化成正指数。 如果用递归实现看起来会更直观，下面用循环实现。

class Solution {
public:
    double Power(double base, int exponent) {
		int tag = 0;
		if (exponent < 1)
		{
			exponent *= -1;
			tag = 1;
		}
		
		double ret = 1;
		while (exponent)
		{
			if (exponent & 1)
			{
				ret *= base;
			}
			
			base *= base;
			exponent >>= 1;
		}
		
		if (tag)
		{
			ret = 1 / ret;
		}
		
		return ret;		
    }
};