剑指 Offer 16. 数值的整数次方

剑指 Offer 16. 数值的整数次方

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

快速幂

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func myPow(x float64, n int) float64 {
    if n < 0 {
        return 1 / myPow(x, -n)
    }

    res := 1.0
    for n != 0 {
        if n & 1 != 0 {    // n % 2 != 0  判断 n 二进制最右边的一位是否为 1，如果为 0 就相当于 res * (x^0) = res
            res = res * x
        }
        x = x * x
        n = n >> 1         // n = n / 2   右移，相当于删除二进制的最右边一位
    }
    return res
}