YSMull
<-- algorithm



原题链接

2021/04/13

二分递归

impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        if n > 0 {
            return Solution::my_pow_i64_rec(x, n as i64);
        } else {
            return 1.0 / Solution::my_pow_i64_rec(x, -(n as i64));
        }
    }
    pub fn my_pow_i64_rec(x: f64, n: i64) -> f64 {
        if n == 0 {
            return 1.0;
        }
        let v = Solution::my_pow_i64(x, n / 2);
        return if n % 2 == 0 { v * v } else { x * v * v };
    }
}

位运算

设 n 的二进制表示为：

\[n = (i_k i_{k-1} \cdots i_0)_2\]

我们有:

\[x^n = x^{i_k\cdot 2^k} \cdot x^{i_{k-1}\cdot 2^{k-1}} \cdot \cdots \cdot x^{i_0\cdot 2^0}\]

注意到如果 $i_m = 0$，那么 $x^{i_m\cdot 2^m} = x^0 = 1$，不影响结果，
所以

\[x^n = \prod\limits_{\substack{i_m=1 \\ 0 <= m <= k}}x^{2^m}\]

同时要注意到：

\[x^{2^{(m+1)}} = (x^{2^m})^2\]

所以，我们从 n 的二进制最低位开始遍历，初始 collector = 1
当遍历到第 m 位时，我们需要保持 x 的值是 $x^{2^m}$,每一次进入下一位，都需要让 x = x^2。（养韭菜）
如果当前位是 1，那么说明我们可以收割这个 x 了，collector = collector * x。（割韭菜）

impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        if n > 0 {
            return Solution::my_pow_i64(x, n as i64);
        } else {
            return 1.0 / Solution::my_pow_i64(x, -(n as i64));
        }
    }

    pub fn my_pow_i64(mut x: f64, mut n: i64) -> f64 {
        let mut collector = 1.0;
        while n > 0 {
            if n & 1 == 1 {
                collector *= x;
            }
            x *= x;
            n >>= 1;
        }
        return collector;
    }
}

2024-07-21 补一个 Java 的，注意 (n & 1) == 1 的括号不能去掉

class Solution {
    public double myPow(double x, int n) {
        if (n > 0) return pow(x, n);
        else return 1.0 / pow(x, -(long) n);
    }

    public double pow(double x, long n) {
        double collector = 1.0;
        while (n != 0) {
            if ((n & 1) == 1) {
                collector *= x;
            }
            x *= x;
            n >>= 1;
        }
        return collector;
    } 
}