6

k>=整数値である2の最小累乗として計算する必要がありますn（n常に> 0です）

現在私は使用しています：

#define log2(x) log(x)/log(2)
#define round(x) (int)(x+0.5)

k = round(pow(2,(ceil(log2(n)))));

これはパフォーマンスが重要な機能にあります

を計算するより計算効率の良い方法はありますkか?

4

6 に答える 6

9 
/* returns greatest power of 2 less than or equal to x, branch-free */
/* Source: Hacker's Delight, First Edition. */
int
flp2(int x)
{
    x = x | (x>>1);
    x = x | (x>>2);
    x = x | (x>>4);
    x = x | (x>>8);
    x = x | (x>>16);
    return x - (x>>1);
}

それを研究し、それがどのように機能するかを見るのは面白いです。どのソリューションが自分の状況に最適であるかを確実に知る唯一の方法は、それらすべてをテキスト フィクスチャで使用してプロファイルし、目的に最も効率的なソリューションを確認することだと思います。

分岐がないため、これは他のいくつかに比べてパフォーマンスの面で非常に優れている可能性がありますが、確認するために直接テストする必要があります.

X 以上の最小の 2 乗が必要な場合は、少し異なるソリューションを使用できます。

unsigned
clp2(unsigned x)
{
    x = x -1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x + 1;
}
于 2013-03-20T14:04:06.160 に答える
2 
lim = 123;
n = 1;
while( ( n = n << 1 ) <= lim );

lim よりも大きくなるまで、数値を 2 倍します。

左に 1 シフトすると、値が 2 倍になります。

于 2013-03-20T14:04:12.187 に答える
2

はい、問題の数値を取得し、ビット シフトを使用して 2 の累乗を決定するだけで、これを計算できます
。 ) 桁。これは、整数除算を 2 で実行するのと同じです。値を左シフトすると、すべてのビットが左に移動し、左端からシフトされたビットが削除され、右端にゼロが追加され、値が実質的に 2 倍になります。数値がゼロになる前に右シフトする必要がある回数を数えると、2 を底とする対数の整数部分が計算されます。次に、それを使用して、値 1 を何回も左シフトして結果を作成します。

  int CalculateK(int val)
  {
      int cnt = 0;
      while(val > 0)
      {
           cnt++;
           val = val >> 1;
      }
      return 1 << cnt;
  }

EDIT：代わりに、もう少し簡単に：カウントを計算する必要はありません

  int CalculateK(int val)
  {
      int res = 1;
      while(res <= val) res <<= 1;
      return res ;
  }
于 2013-03-20T14:05:35.437 に答える
2 
int calculate_least_covering_power_of_two(int x)
{
  int k = 1;
  while( k < x ) k = k << 1;
  return k;
}
于 2013-03-20T14:17:54.957 に答える
1 
k = 1 << (int)(ceil(log2(n)));

2 進数は 2 の累乗を表すという事実を利用できます (1 は 1、10 は 2、100 は 4 など)。1 を 2 の指数で左にシフトすると、同じ値が得られますが、はるかに高速です。

ただし、どうにかして ceil(log2(n)) を回避できれば、パフォーマンスが大幅に向上します。

于 2013-03-20T14:02:47.903 に答える
1

ソース: hackersdelight.org

/* altered to: power of 2 which is greater than an integer value */

unsigned clp2(unsigned x) {
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x + 1;
}

以下を追加する必要があることに注意してください。

x = x | (x >> 32);

64 ビットの数値の場合。

于 2013-03-20T14:21:24.543 に答える