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 mpowernアルゴリズムが機能するのと同じように機能します。次の2セットの入力のコードをトレースするだけです。

PS：ansは1に設定する必要があります。

1. n = 2
2. n = 3

きっとあなたはそれを手に入れるでしょう。