两种方法求x的n次幂

一、递归方法

分析:
在求一个数x的n次幂时,可分为偶数和奇数两种情况来讨论,若x为偶数,则x^n=x^n/2 * x^n/2,若果x为奇数,则x^n=x^(n-1)/2 * x^(n-1)/2 * x。它的基准情况(无需递归即能解出)很明显,就是n==0和n==1时,n==0时,则任何数的0次幂均为1,n==1时,任何数的1次幂均为它本身。

有了上述分析后,代码就很容易写出了。

public class Pow {
    public static void main(String[] args) {
        System.out.println(pow(2, 5));
        System.out.println(pow(2, 10));
    }
    /*
     * 求x得n次幂
     */
    public static long pow(long x,long n){
        if(n==0){
            return 1;
        }
        if(n==1){
            return x;
        }
        if(x%2==0){
            return pow(x*x, n/2);
        }else{
            return pow(x*x, n/2)*x;
            /*return pow(x, n-1)*x;*/
            //n为奇数时,n-1即为偶数,因此可以写成x^n=x^n-1 * x,
            //因为x^n-1的值是偶数次幂情况时已求出
        }
    }

}

二、非递归方法

例子:
求x^5的值
5可以转成二进制,即101,5=2^2+2^0。
x^5因此可以写成x的2^2+2^0次幂。

我们知道一个数n,刚开始n%2==1的话,说明它转成二进制时,最低位为1,否则为0,下面进行n=n/2(n=n>>1)(右移操作);
如果再次进行n%2==1的话,说明此时的最低位为1,否则为0。

综上利用以上特性

public class Question23 {
    public static void main(String[] args) {
                System.out.println(Pow(3, 3));
                //27
    }

    public static int Pow(int x, int n) {
        int s = 1;
        while (n > 0) {
            if (n % 2 == 1)
                s *= x;
            x *= x;
            n >>= 1;//n=n/2;
        }
        return x;
    }
}

如果看不懂,不理解就找个例子代入,比如求4^11。
初始值x=4,n=11,s=1。
11的二进制表示为1011=1x2^3+0x2^2+1x2^1+1x2^0
第一次循环,n%2=1条件满足,s=4的1次方,x=4的2次方,n向右移动一位,即101
第二次循环,n%2=1条件满足,s=4的3次方,x=4的4次方,n继续向右移动一位,即10
第三次循环,n%2=1条件不满足,s=4的3次方没变,x=4的8次方,n继续向右移动一位,即1
第四次循环,n%2=1条件满足,s=4的11次方,此时x=4的16次方,n继续向右移动一位,即0
n>0条件不满足,结束循环。

看完这个过程,就应该明白了以下:
1011
       ↑
101
     ↑
10
  ↑
1
 ↑

1、x存在根本上是为了获得箭头所指的数在原本的数中的位权,因此依次为1,2,4,8
2、s存在根本上是为了求箭头所指数的和,因此为1,3,11。1101,其它位都为1,只有第三位为0,所以由3直接到11。
(4只是底数,不产生影响)

如果到这还不明白,建议多走几遍流程,便理解了。

For man is man and master of his fate