Power of Two

n = 2^k なら、k 回ちょうど 2 で割ると 1 になり、その途中の値はすべて偶数です。n に 1 より大きい奇数の因数がある場合、半分にする操作は 1 ではない奇数で止まります。16 の場合：16, 8, 4, 2, 1 なので、答えは true です。24 の場合：24, 12, 6, 3 となり、3 は奇数ですが 1 ではないため、答えは false です。

ループの前に n ≤ 0 なら false を返します。2 のべき乗が 0 または負になることはなく、0 は偶数であり、0 の半分も 0 のままなので、ループが 0 で終了することはありません。

各ステップで n は半分になるため、32 ビット入力でのステップ数は最大 31 回です。時間計算量は O(log n)、空間計算量は O(1) です。

2 のべき乗を2進数で書くと、1つの 1 の後にゼロが続きます。16 は 10000 です。1 を引くと、その 1 が 0 になり、その下にあるすべての 0 が 1 になります。15 は 01111 です。この2つの数には共通する 1 ビットがないため、16 & 15 は 0 です。

それ以外の正の数には、少なくとも2つの 1 ビットがあります。1 を引くと、最も下位の 1 ビットとその下のゼロだけが変化するため、それより上位の 1 ビットは両方の数に現れ、AND の結果は 0 になりません。11000 である 24 の場合、23 = 10111 となり、24 & 23 は 10000、つまり 16 です。

まず n > 0 を確認してください。0 & -1 は 0 であり、32ビット演算では -2^31 は1つの 1 ビットの後に31個のゼロが続くため、AND だけではどちらも2のべき乗と判定されてしまいます。テスト全体は比較1回、減算1回、AND 1回で、時間計算量と空間計算量は O(1) です。Lua 5.1 には AND 演算子がないため、Lua のコードでは一度に1ビットずつ AND を構築します。32ビットの n では最大31ステップです。テストは同じです。