【递归】高效率求2的n次幂

思路：使用翻一番的技巧。

比如，2的9次 则 1 * 2 = 2；2 * 2 = 4；4 * 4 =16；16 * 16=。。。；

指数：1-----------2-----------4------------8---------------

对应代码：

能翻倍的情况下

//能翻
while((ex<<1)<n) {
			//翻
			res = res * res;
			//指数实际增长
			ex<<=1;
		}
           

不能翻倍的情况下

不能翻：则把差值作为指数递归计算。

当差值为0时，就说明到头了，只剩最后一个数字。 return 1 。乘数字本身即可。

代码如下

static int pow (int a,int n) {
		if( n == 0){
			return 1;
		}
		int res = a;
		int ex = 1;
		//判断能不能翻倍
		while((ex<<1)<n) {
			//翻
			res = res * res;
			//指数实际增长
			ex<<=1;
		}
		//不能翻：则把差值作为指数递归计算。
		// 当差值为0时，就说明到头了，只剩最后一个数字。 return 1 。乘数字本身即可。
		return res*pow(a, n-ex);
	}
	
	public static void main(String[] args) {
		System.out.println(pow(2, 3));
	}