c - n より大きい 2 の最小べき乗を見つける

Question

32 ビット整数 n より大きい最小の 2 のべき乗を見つけるためのコードに出くわしました...

n+=(n==0);
n--;
n|=n>>1;
n|=n>>2;
n|=n>>4;
n|=n>>8;
n|=n>>16;
n++;

今、それはどのように機能しますか？n=100 の場合、各ステップの後に基数 2 で数値を出力しようとしましたが、あまり意味がありませんでした。その背後にあるロジックは何ですか？

Answer 1

このコードは、指定された数値のすべての最下位ビットnをバイナリ1s で埋め、その後、結果を だけ増やして1、要求された結果を達成します。たとえば、入力101の場合、ビット操作は生成され、それ111による増加後は(8) になります。これは実際には(5)より大きい 2 の最小累乗です。11000101

更新: 実際には、これは各 lsb ビットを手動で設定するだけの簡単な方法に対する最適化です。この最適化が同じ結果を達成する理由は、この問題を超えたより広い範囲での別の問題です。

Answer 2

実際には、2 の累乗以上の最小値を検出し、n32 ビットの符号なし数値に対して機能します。

• 最初の行は、0 を 1 と同じように扱っているだけです (やや紛らわしい方法で記述されています)。
• 2 行目は「または等しい」を説明します。数値が正確に 2 の累乗である場合は、1 ビット短くします。
• 次の数行では、すべての下位ビットが 1 に設定されていることを確認します。最初に、右に 1 シフトし、論理 OR を実行します。その結果、最上位ビットとそのすぐ下のビットが 1 に設定されます。2 のシフトで同じことを行うと、上位 4 ビットが 1 になります。
• 最後に、2 のべき乗よりも 1 小さい数が得られ、1 を足すだけです。

Answer 3

icepack の回答への追加: hereで説明されているように、アルゴリズムは を計算し1 << (floor(log_2(n - 1)) + 1)ます。