有人可以解释这个C代码如何计算2 ^ n？

Question

这是诀窍的代码.我知道如何在O(logn)时间内计算m ^ n的概念,我认为它是相关的,但是如何？

for(long long int i = 2; N; N /= 2, i *= i){
    if(N & 1){
        ans *= i;
    }
}

Answer 1

这是方形和乘法算法.

N/= 2具有去除最低位的效果(并且当剩余的所有位都为零时,算法结束).

N&1检查最低位是奇数还是偶数