快速幂

递归快速幂

写成代码是这样的：

package cn.meowrain;
public class Main {
	public static void main(String[] args) {
		int n = 7;
		System.out.println(qpow(2, n));
	}
	static int qpow(int a,int n) {
		if(n == 0) return 1;
		else if(n%2==1) { //如果n是奇数(odd)
			return qpow(a, n-1)*a;
		}
		else { //如果n是偶数
			int temp = qpow(a, n/2);
			return temp*temp;
		}
	}
}

递归会产生额外内存开销，可以使用循环来重写

非递归快速幂

我TM直呼妙哉！

package cn.meowrain;


public class Main {
    public static void main(String[] args) {
        System.out.println(qpow(2, 3));
    }
    static int qpow(int a,int n) {
    	int ans = 1;
    	while(n!=0) {
    		if((n&1) == 1){ ////如果n的当前末位为1
    			ans*=a;//如果n的当前末位为1
    		}
    		a*=a;//如果n的当前末位为1
    		n>>=1; //n往右移一位
    	}
    	return ans;
    }
}