c - このコードは、任意の数値に対して次に高い 2 の累乗を見つけるためにどのように機能しますか?

Question

このコードは、32 ビット整数の任意の数値 [>1] に対して次に高い 2 の累乗を見つけるためにどのように機能しますか?

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

Answer 1

一連のシフトとビットごとの論理和により、12 のべき乗よりも 1 小さい、すべての s で構成される数値が保証されます。これに 1 を加えると、2 のべき乗が得られます。

最初の 1 の減少は、n既に 2 の累乗になっている の値に対して機能させるためのものです。

n(明らかに、このコードは元が の場合は機能しません0。)

Answer 2

The decrement will make the case 2 ^ n to give the result 2 ^ n instead of 2 ^ (n + 1). It does not correspond to the increment at the end.

The part between decrement and increment actually tries to fill up all the bit that is less significant than the currently most significant bit that is 1. The highest bit that is 1 will gradually propagate after each line and will fill up all the less significant bits by the last line.

The increment is to get to the result of the next highest power of 2.