leetcode50.Pow(x,n)

Question

//实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。 
//
// 
//
// 示例 1： 
//
// 
//输入：x = 2.00000, n = 10
//输出：1024.00000
// 
//
// 示例 2： 
//
// 
//输入：x = 2.10000, n = 3
//输出：9.26100
// 
//
// 示例 3： 
//
// 
//输入：x = 2.00000, n = -2
//输出：0.25000
//解释：2-2 = 1/22 = 1/4 = 0.25
// 
//
// 
//
// 提示： 
//
// 
// -100.0 < x < 100.0 
// -231 <= n <= 231-1 
// -104 <= xn <= 104 
// 
// Related Topics 递归 数学 
// 👍 763 👎 0

Answer

$x^n\,:\,3^5\,:\,x=3, \,n=5$

n二进制表示0101，n«1表示n*=2，n»1表示n/=2。
n&1==1表示最后一位是1，n&1==0表示最后一位是0。
对n做右移一位操作，n最后一位是1即做ret与x累乘。

$n=5=2^2+2^0$

n=0101	ret=1*3=3	x=3*3=9
n=0010		x=9*9=81
n=0001	ret=3*81=243	x=81*81=6561
n=0001
n=0000
return

n=1010		x=2*2=4
n=0101	ret=1*4=4	x=4*4=16
n=0010		x=16*16=256
n=0001	ret=4*256=1024	x=256*256
n=0000
return

double myPow(double x, int n) {
    // x:2, n:10 (1010)
    //n<<1,*2; n>>1,/2
		double ret = 1;
    if (n<0) {
        x = 1/x;
    }
    long long k = abs((long long)n);	//防止超时

    while (k) {
        if (k&1) {
            //n的最后一位是1
            ret *= x;
        }
        x *= x;
        k = k>>1;
        cout << "x:" << x << endl;
    }

    return ret;
}

x = 1.00000， n = -2147483648，long long存n，防止溢出
x = 2.00000， n = -2

Question

Answer

CATALOG

FEATURED TAGS