c++ - 有人能解释一下这个 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 检查最低位是奇数还是偶数

Answer 2

它的工作方式基本上与 log N time m power n 算法的工作方式相同。只需跟踪这两组输入的代码：

PS：ans 应设置为 1。

1. n=2
2. n=3

我相信你会得到它。