ある整数が与えられたとき、ビット操作で次に大きい2のべき乗を求めるにはどうすればよいですか？

質問

もし、整数の n があるとすると、次の数字 k > n を求めることができます。 k = 2^i で、ある i の要素を N をビット単位でシフトするか、論理で指定します。

例 もし私が n = 123 がある場合、どのようにして k = 128 でなく、2のべき乗である 124 は2の累乗であり、2で割り切れるだけのではありません。これは簡単なはずなのですが、私には理解できません。

どうすればいいのでしょうか？

32ビット整数の場合、これは単純で簡単なルートです。

unsigned int n;

n--;
n |= n >> 1;   // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2;   // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;           // The result is a number of 1 bits equal to the number
               // of bits in the original number, plus 1. That's the
               // next highest power of 2.

より具体的な例を挙げましょう。221という数字を例にとると、2進数で11011101となります。

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1100 | 0110 1110 = 1111 1110
n |= n >> 2;   // 1111 1110 | 0011 1111 = 1111 1111
n |= n >> 4;   // ...
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

9番目の位置に1ビットあり、これは2^8を表します、つまり 256 を表し、これは確かに 2 の次の大きな累乗です。 . 各シフトは、数値の既存のすべての1ビットに、それまで手をつけられていなかったいくつかの0を重ね、最終的に元の数値のビット数に等しい数の1ビットを生成します。この値に1を足すと、新しい2の累乗が生成されます。

もう一つの例として、131を使用します。これは2進数で10000011です。

n--;           // 1000 0011 --> 1000 0010
n |= n >> 1;   // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2;   // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4;   // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8;   // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16;  //      operations produce no effect.)
n++;           // 1111 1111 --> 1 0000 0000

そして実際、256は131の次に大きい2のべき乗です。

整数を表現するために使用するビット数自体が2の累乗であれば、この手法を効率よく無限に拡張し続けることができます（例えば、この手法に n >> 32 行を追加して64ビット整数を表現するなど)。