public class A的N次幂 {

	public static void main(String[] args) {

		int a = 2;

		int n = 60;

		long t = System.nanoTime();   // 纳秒

		System.out.println(pow0(a, n));

		System.out.println("pow0()所花时间："+(System.nanoTime()-t)+"ns");

		t = System.nanoTime();

		System.out.println(pow(a, n));

		System.out.println("pow()所花时间："+(System.nanoTime()-t)+"ns");

	}

	// O(N)

	private static long pow0(int a,int n){

		long res = 1;

		for(int i=0;i<n;i++){

			res *= a;

		}

		return res;

	}

	private static long pow(int a,int n){

		if (n==0) {

			return 1;

		}

		long res = a;

		int ex = 1;

		while((ex<<1)<=n){

			res = res * res;

			ex <<=1;

		}

		return res*pow(a, n-ex);

	}

}