快速幂及二進制複習

• Leetcode劍指offer第16題（快速幂）

class Solution {
public:
    double myPow(double x, int n) {
        if(x==0) return 0;
        long b=n;
        double res=1;
        if(n<0){
            x = 1/x;
            b = -b;
        }
        while(b){
            if(b&1){
                res *=x;
                b--;
            }
            x *=x;
            b>>=1;
        }
        return res;
    }
};
           

class Solution(object):
    def myPow(self, x, n):
        if x==0: return 0;
        res =1
        if n<0: 
            n=-n
            x=1/x
        while n:
            if n&1:
                res*=x
            x*=x
            n>>=1
        return res
           

此圖來自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.轉自知乎，二進制十進制互相轉換

https://zhuanlan.zhihu.com/p/75291280

2.轉自知乎，位運算符

https://zhuanlan.zhihu.com/p/92620039

簡單舉例：

int a

a&1==1 如果成立表示a為奇數，即a二進制最後一位是1

a>>2相當于a/2，a<<2相當于a*2