☰

2の累乗に切り上げる 質問する

tag-icon • tag-icon c optimization bit-manipulation
2の累乗に切り上げる 質問する

最も近い 2 の累乗数を返す関数を記述したいと思います。たとえば、入力が 789 の場合、出力は 1024 になります。ループを使用せずにビット演算子のみを使用してこれを実現する方法はありますか?

関連している：与えられた値以上の 2 の最小の累乗を求めるアルゴリズムC++ に関する質問です。C++20 が導入され、std:bit_ceilコンパイラはターゲット システムに最適な操作を実行できるようになりましたが、ほとんどの CPU が備えているビット スキャン、ポップカウント、その他の一般的なビット操作については、移植可能な ISO C で同等の機能がまだ用意されていません。移植可能な C コードは、効率が悪く、より複雑になるか、またはその両方になります。

整数が与えられた場合、ビット操作を使用して次に大きい 2 の累乗を見つけるにはどうすればよいですか?constexprこれは、GNU 拡張機能を使用したC++11 と 17 を使用した、言語に依存しない質問のバージョンです。

この質問に対する回答は移植可能である必要はありません。さまざまなプラットフォーム用の高速バージョンが役立ちます。

ベストアンサー1

チェックしてくださいビットをいじるハック2 を底とする対数を取得し、それに 1 を加算する必要があります。32 ビット値の例:

2の次の累乗に切り上げる

unsigned int v; // compute the next highest power of 2 of 32-bit v

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

他の幅への拡張は明らかです。

回答整数が与えられた場合、ビット操作を使用して次に大きい 2 の累乗を見つけるにはどうすればよいですか?どのように動作するかについての説明と、いくつかの入力に対するビットパターンの例を示します。

おすすめ記事