これが私のお気に入りです。無効かどうかの最初のチェック (<0、渡された数値が >=0 しかないことがわかっている場合はスキップできます) 以外は、ループや条件がないため、他のほとんどの方法よりも優れています。これはエリクソンの答えに似ていますが、最初に x を減らし、最後に 1 を追加することは、彼の答えよりも少し厄介ではないと思います (また、最後の条件を回避します)。
/// Round up to next higher power of 2 (return x if it's already a power
/// of 2).
inline int
pow2roundup (int x)
{
if (x < 0)
return 0;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x+1;
}
ceil(log2(value))
ilog2()3 つの asm 命令で計算できます。例: http://www.asterisk.org/doxygen/1.4/log2comp_8h-source.html
Intel ハードウェアでは、BSR 命令は必要なものに近く、最も重要なセット ビットを見つけます。より正確にする必要がある場合は、残りのビットが正確にゼロかどうか疑問に思うことができます。私は、他の CPU には BSR のようなものがあると想定する傾向があります。これは、数値を正規化するために答えてほしい質問です。数値が 32 ビットを超える場合は、最も重要な DWORD からスキャンを実行して、ANYビットが設定された最初の DWORD を見つけます。Edsger Dijkstra はおそらく、上記の「アルゴリズム」はコンピュータが 2 進数字を使用していることを前提としていると言うでしょうが、彼のような高尚な「アルゴリズム」の観点からは、チューリング マシンか何かについて考える必要があります - 明らかに私はより実用的なスタイルです。
Quake II の 0x5f3759df と Bit Twiddling Hacks の IEEE バージョンの精神に基づいて、このソリューションは double に到達し、floor(lg2(n)) を計算する手段として指数を抽出します。これは、浮動小数点演算を回避するため、受け入れられているソリューションよりも少し速く、Bit Twiddling IEEE バージョンよりもはるかに高速です。コーディングされているように、double はリトルエンディアン マシン上の実数*8 IEEE float であると想定しています。
int nextPow2(int n)
{
if ( n <= 1 ) return n;
double d = n-1;
return 1 << ((((int*)&d)[1]>>20)-1022);
}
編集: 同僚の助けを借りて、最適化された x86 アセンブリ バージョンを追加します。速度は 4% 向上しますが、bsr バージョンよりも約 50% 遅くなります (n=1..2^31-2 の場合、私のラップトップでは 4 秒に対して 6 秒)。
int nextPow2(int n)
{
if ( n <= 1 ) return n;
double d;
n--;
__asm {
fild n
mov eax,4
fstp d
mov ecx, dword ptr d[eax]
sar ecx,14h
rol eax,cl
}
}
Here's a template version of the bit shifting technique.
template<typename T> T next_power2(T value)
{
--value;
for(size_t i = 1; i < sizeof(T) * CHAR_BIT; i*=2)
value |= value >> i;
return value+1;
}
Since the loop only uses constants it gets flattened by the compiler. (I checked) The function is also future proof.
Here's one that uses __builtin_clz. (Also future proof)
template<typename T> T next_power2(T value)
{
return 1 << ((sizeof(T) * CHAR_BIT) - __builtin_clz(value-1));
}
pow ( 2 , ceil( log2(値) );
log2(値) = ログ(値) / ログ(2);
あなたの実装はナイーブではありません。実際には論理的なものですが、間違っていることを除けば、最大整数サイズの 1/2 を超える数値に対して負の値を返します。
数値を 0 ～ 2^30 の範囲 (32 ビット整数の場合) に制限できると仮定すると、問題なく機能し、対数を含む数学関数よりもはるかに高速になります。
符号なし int の方が適切に機能しますが、 << 演算子では 2^32 に到達できないため、(2^31 より大きい数値の場合) 無限ループになってしまいます。
密接に関連する問題（つまり、切り上げではなく切り捨て）の可能な解決策の調査は、単純なアプローチよりも大幅に高速であり、この種の最適化を行うための優れたリソースであるBitTwiddlingHacksページで入手できます。あなたは探している。最速の解決策は、256エントリのルックアップテーブルを使用することです。これにより、単純なアプローチの平均62（同様の操作カウント方法による）から、合計操作カウントが約7に減少します。これらのソリューションを問題に適応させることは、単一の比較と増分の問題です。
「より良いアルゴリズム」の意味を実際には言いませんが、提示したものは完全に明確であるため（多少欠陥がある場合）、より効率的なアルゴリズムを求めていると思います。
Larry Gritz は、ルックアップ テーブルのオーバーヘッドがなく、おそらく最も効率的な c/c++ アルゴリズムを示しており、ほとんどの場合はそれで十分です (同様のアルゴリズムについては、 http: //www.hackersdelight.org を参照してください)。
他の場所で述べたように、最近のほとんどの CPU には、先行ゼロの数をカウントする (または同等にミリ秒セット ビットを返す) マシン命令がありますが、それらの使用は移植性がなく、ほとんどの場合、努力する価値はありません。
ただし、ほとんどのコンパイラには、マシン命令の使用を可能にする「組み込み」関数がありますが、より移植性の高い方法で使用できます。
Microsoft C++ には _BitScanReverse() があり、gcc には __builtin_clz() が用意されており、大量の作業を効率的に実行できます。
これがダウンボットベイトであることは知っていますが、数が十分に小さい場合（8ビットや16ビットなど）、直接ルックアップが最も高速な場合があります。
// fill in the table
unsigned short tab[65536];
unsigned short bit = tab[i];
最初に上位ワードを実行し、次に下位ワードを実行することで、32ビットに拡張できる場合があります。
//
unsigned long bitHigh = ((unsigned long)tab[(unsigned short)(i >> 16)]) << 16;
unsigned long bitLow = 0;
if (bitHigh == 0){
bitLow = tab[(unsigned short)(i & 0xffff)];
}
unsigned long answer = bitHigh | bitLow;
シフトまたはメソッドよりも優れているとは言えませんが、より大きなワードサイズに拡張できる可能性があります。
（実際には、これにより最高の1ビットが得られます。次に高い2の累乗を得るには、1ビット左にシフトする必要があります。）
以下のコードは、数値が2の累乗になるまで最下位ビットを繰り返し削除し、数値が最初から2の累乗でない限り、結果を2倍にします。設定されたビット数に比例した時間で実行できるという利点があります。残念ながら、ほとんどの場合、質問のコードやアセンブリの提案よりも多くの命令が必要になるという欠点があります。完全を期すためにのみ含めます。
int nextPow(int x) {
int y = x
while (x &= (x^(~x+1)))
y = x << 1;
return y
}
同じの私のバージョン：
int pwr2Test(size_t x) {
return (x & (x - 1))? 0 : 1;
}
size_t pwr2Floor(size_t x) {
// A lookup table for rounding up 4 bit numbers to
// the nearest power of 2.
static const unsigned char pwr2lut[] = {
0x00, 0x01, 0x02, 0x02, // 0, 1, 2, 3
0x04, 0x04, 0x04, 0x04, // 4, 5, 6, 7
0x08, 0x08, 0x08, 0x08, // 8, 9, 10, 11
0x08, 0x08, 0x08, 0x08 // 12, 13, 14, 15
};
size_t pwr2 = 0; // The return value
unsigned int i = 0; // The nybble interator
for( i = 0; x != 0; ++i ) { // Iterate through nybbles
pwr2 = pwr2lut[x & 0x0f]; // rounding up to powers of 2.
x >>= 4; // (i - 1) will contain the
} // highest non-zero nybble index.
i = i? (i - 1) : i;
pwr2 <<= (i * 4);
return pwr2;
}
size_t pwr2Size(size_t x) {
if( pwr2Test(x) ) { return x; }
return pwr2Floor(x) * 2;
}
私はシフトが大好きです。
落ち着く
int bufferPow = 1;
while ( bufferPow<bufferSize && bufferPow>0) bufferPow <<= 1;
そうすれば、ループは常に終了し、&&の後の部分はほとんど評価されません。そして、私は2行が関数呼び出しの価値があるとは思いません。また、あなたの判断に応じて、長くしたり短くしたりすることができ、非常に読みやすくなっています。（bufferPowが負になった場合、メインコードがすぐに終了することを願っています。）
通常、アルゴリズムの開始時に2乗を計算するのは一度だけなので、とにかく最適化はばかげています。しかし、退屈している人がスピードコンテストの世話をするのであれば興味があります...上記の例と255 256 257 .. 419541964197を使用して
任意の対数関数は、2 の対数で除算することにより、底が 2 の対数に変換できます。
$ /usr/local/pypy-1.9/bin/pypy
Python 2.7.2 (341e1e3821ff, Jun 07 2012, 15:38:48)
[PyPy 1.9.0 with GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``<arigato> yes but there is not
much sense if I explain all about today's greatest idea if tomorrow it's
completely outdated''
>>>> import math
>>>> print math.log(65535)/math.log(2)
15.9999779861
>>>> print math.log(65536)/math.log(2)
16.0
>>>>
もちろん、浮動小数点演算が含まれているため、100% 正確というわけではありません。
これは機能し、非常に高速です（2.66 GHz Intel Core 2 Duo 64ビットプロセッサで）。
#include <iostream>
int main(void) {
int testinput,counter;
std::cin >> testinput;
while (testinput > 1) {
testinput = testinput >> 1;
counter++;
}
int finalnum = testinput << counter+1;
printf("Is %i\n",finalnum);
return 0;
}
3、6、および65496でテストしたところ、正解（4、8、および65536）が得られました。
これが少し難解に思えるなら申し訳ありませんが、私は書く直前に数時間のドゥームの影響を受けていました。:)