学步园

求a的n次方，要求快速算法。

求一个数的n（n是int型正整数）次方，比较简单的题目，但是也有比较大的优化空间。

图片是求a的n次方的公式。

如果n是偶数、.....如果n是奇数、.....

可以看出是一个递推公式的样子，可以用递归来解决。

package static_;

public class Test {

	public static void main(String[] args) throws Exception {
		System.out.println(6 & 0x1);
	}

	public static double func(int a, int exponent) {
		if (exponent == 1) {
			return a;
		}
		if (exponent == 0) {
			return 1;
		}
		double d = func(a, exponent >> 1);
		d = d * d;
		if ((exponent & 1) == 1) {// 如果exponent是奇数
			d *= a;
		}
		return 1;
	}
}

在普通的用n次乘法求a的n次方的算法中，时间复杂度就是o(n)，在本算法中，时间复杂度是o(logn)，但是也伴随了空间复杂度o(logn)。