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

Question

最も近い次の 2 のべき乗を返す関数を書きたいと思います。たとえば、入力が 789 の場合、出力は 1024 である必要があります。ループを使用せずにビット単位の演算子を使用するだけでこれを達成する方法はありますか?

score 189 · Accepted Answer

Bit Twiddling Hacksを確認してください。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++;

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

score 85 · Accepted Answer

next = pow(2, ceil(log(x)/log(2)));

これは、xを取得するために2を上げた数を見つけることによって機能します（数の対数を取り、目的のベースの対数で除算します。詳細については、ウィキペディアを参照してください）。次に、それをceilで切り上げて、最も近い整数の累乗を取得します。

これは、他の場所にリンクされているビット単位のメソッドよりも汎用的な（つまり遅い！）メソッドですが、数学を知っておくとよいでしょう。

score 68 · Accepted Answer

これもうまくいくと思います：

int power = 1;
while(power < x)
    power*=2;

答えはpowerです。

score 53 · Accepted Answer

unsigned long upper_power_of_two(unsigned long v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;

}

score 40 · Accepted Answer

GCC を使用している場合は、Optimizing the next_pow2() function by Lockless Inc. を参照してください。このページでは、組み込み関数builtin_clz()(先行ゼロをカウント) を使用し、後で x86 (ia32) を直接使用する方法について説明します。別の回答のgamedevサイトへのリンクbsrで説明されているのと同じように、アセンブラー命令（ビットスキャンリバース）。このコードは、前の回答で説明したコードよりも高速である可能性があります。

ちなみに、アセンブラ命令と64ビットデータ型を使わない場合は、これを使用できます

/**
 * return the smallest power of two value
 * greater than x
 *
 * Input range:  [2..2147483648]
 * Output range: [2..2147483648]
 *
 */
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 1);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif

    return 1 << (32 - __builtin_clz (x - 1));
}

score 19 · Accepted Answer

もう1つ、サイクルを使用していますが、これは数学オペランドよりもはるかに高速です

2 のべき乗「フロア」オプション:

int power = 1;
while (x >>= 1) power <<= 1;

2 のべき乗「ceil」オプション:

int power = 2;
x--;    // <<-- UPDATED
while (x >>= 1) power <<= 1;

アップデート

コメントで述べたようにceil、結果が間違っていた場所に間違いがありました。

完全な機能は次のとおりです。

unsigned power_floor(unsigned x) {
    int power = 1;
    while (x >>= 1) power <<= 1;
    return power;
}

unsigned power_ceil(unsigned x) {
    if (x <= 1) return 1;
    int power = 2;
    x--;
    while (x >>= 1) power <<= 1;
    return power;
}

score 9 · Accepted Answer

IEEE フロートの場合、次のようなことができます。

int next_power_of_two(float a_F){
    int f = *(int*)&a_F;
    int b = f << 9 != 0; // If we're a power of two this is 0, otherwise this is 1

    f >>= 23; // remove factional part of floating point number
    f -= 127; // subtract 127 (the bias) from the exponent

    // adds one to the exponent if were not a power of two, 
    // then raises our new exponent to the power of two again.
    return (1 << (f + b)); 
}

整数ソリューションが必要で、インラインアセンブリを使用できる場合、BSR は x86 上の整数の log2 を提供します。正しいビットがいくつ設定されているかをカウントします。これは、その数値の log2 に正確に等しくなります。他のプロセッサには、(多くの場合) CLZ などの同様の命令があり、コンパイラによっては、作業を行うための組み込み関数が利用できる場合があります。

score 6 · Accepted Answer

x86 では、sse4 ビット操作命令を使用して高速化できます。

//assume input is in eax
mov    ecx,31      
popcnt edx,eax   //cycle 1
lzcnt  eax,eax   //cycle 2
sub    ecx,eax
mov    eax,1
cmp    edx,1     //cycle 3
jle @done        //cycle 4 - popcnt says its a power of 2, return input unchanged
shl    eax,cl    //cycle 5
@done: rep ret   //cycle 5

c では、対応する組み込み関数を使用できます。

または、ジャンプによる予測ミスを回避することで速度を上げますが、依存チェーンを長くすることで速度を落とします。コードの時間を計って、どれが最適かを確認してください。

//assume input is in eax
mov    ecx,31
popcnt edx,eax    //cycle 1
lzcnt  eax,eax
sub    ecx,eax
mov    eax,1      //cycle 2
cmp    edx,1
mov    edx,0     //cycle 3 
cmovle ecx,edx   //cycle 4 - ensure eax does not change
shl    eax,cl    
@done: rep ret   //cycle 5

score 5 · Accepted Answer

/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000)         ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00)             ? (8  +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0)               ? (4  +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc)                ? (2  +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2)                ? (1)                  : (0))

#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8  __LOG2D

static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
    return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
    i =i -1;
    i =LOG2_UINT64(i);
    return 1UL <<(1 +i);
#endif
}

未定義の動作の領域に足を踏み入れたくない場合は、入力値を 1 ～ 2^63 にする必要があります。このマクロは、コンパイル時に定数を設定するのにも役立ちます。

score 4 · Accepted Answer

完全を期すために、ボグ標準 C での浮動小数点実装をここに示します。

double next_power_of_two(double value) {
    int exp;
    if(frexp(value, &exp) == 0.5) {
        // Omit this case to round precise powers of two up to the *next* power
        return value;
    }
    return ldexp(1.0, exp);
}

score 0 · Accepted Answer

x==1x86プラットフォーム、コンパイラ、gcc、またはclangに対してのみ有効な@YannDroneaud回答のバリアント：

__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
    assert(x > 0);
    assert(x <= ((UINT32_MAX/2) + 1));
#endif
  int clz;
  uint32_t xm1 = x-1;
  asm(
    "lzcnt %1,%0"
    :"=r" (clz)
    :"rm" (xm1)
    :"cc"
    );
    return 1 << (32 - clz);
}

score -1 · Accepted Answer

OpenGL関連のものに必要な場合：

/* Compute the nearest power of 2 number that is 
 * less than or equal to the value passed in. 
 */
static GLuint 
nearestPower( GLuint value )
{
    int i = 1;

    if (value == 0) return -1;      /* Error! */
    for (;;) {
         if (value == 1) return i;
         else if (value == 3) return i*4;
         value >>= 1; i *= 2;
    }
}

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

31 に答える 31

Related

Reference