5

数値をその下の最大の整数に丸めるフロア関数のように、数値のバイナリベースを見つけようとしています。数値をその下の最初のバイナリベースに丸めたいです。

例えば：

for 1000 it should be 512
for 10 it should be 8
for 208 it should be 128

これは私が試したものです。ログ関数はより多くのリソースを消費すると思うので、これに対するより速いアプローチはありますか?

#include<stdio.h>
int main()  {
    unsigned long long int num;
    unsigned long long int mask;
    scanf("%llu", &num);
    mask = 0x80000000;
    while(mask >>= 1)   {
        if (mask & num)
            break;
    }
    printf("%llu\n", mask);
    return 0;
}

ありがとう：）

4

11 に答える 11

2

この古典的なドキュメントには、整数の下限 (底が 2 の対数) を見つける多くの方法があります。ログを見つけた後、必要な数はもちろん 1 << ログです。

最も魅力的な提案はこれです

// Find the integer log base 2 of an integer with an 64-bit IEEE float 
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

上記のコードは、指数が 252 に設定されている間、仮数部に整数を格納することにより、64 ビット (IEEE-754 浮動小数点) double に 32 ビット整数 (パディング ビットなし) をロードします。この新しく作成された double から、 252 (double として表される) が減算され、結果の指数が入力値 v の対数底 2 に設定されます。残っているのは、指数ビットを位置 (20 ビット右) にシフトし、バイアス 0x3FF を減算することだけです (これは 10 進数の 1023 です)。この手法は 5 つの操作しか必要としませんが、多くの CPU は double の操作が遅く、アーキテクチャのエンディアンに対応する必要があります。

したがって、必要な最終結果は になります1 << r。double の操作は、この記事が書かれたときよりもはるかに高速になっていることに注意してください。このコードの最も良い点は、分岐が含まれていないため、うまくパイプライン処理されることです。ぜひ試してみてください。今はベンチマークを試す時間はありませんが、興味深いでしょう。

このコードが C 標準に準拠しているとは保証できません。

于 2013-05-30T13:42:25.787 に答える
1

これは、最も重要なビットの問題を見つけることに非常に密接に関連している問題です。その後は少しだけシフトしているためです。

MSB の検索については、ここで詳しく説明されています。

ビット配列に設定されている最上位ビット (一番左) を見つける

そして、あなたはこのようなことをします:

int foo = 1000;
int bar = ((msb(foo) << 1) - 1) >> 1; 
if ( bar > foo ) bar = bar >> 1;

そしてあなたはそれを持っています。

Intel アーキテクチャを使用している場合は、gcc で __builtin_clz (先頭のゼロを計算) を使用して msb を取得できます。

または

これは、CPU サポートなしで先行ゼロを計算する本当に楽しい方法です。

http://www.hackersdelight.org/hdcodetxt/nlz.c.txt

于 2013-05-30T02:47:10.847 に答える
1

短くて甘い...
(Questioner のサンプル コードでは、値 >= 0x80000000LLU で問題がありました。ここで修正されました。)
これは、ループ内で 2 回ではなく 1 回の比較しか必要としません。

unsigned long long int MSMask(unsigned long long int) {
  if (num == 0) {
    return 0;
    }
  else {
    unsigned long long int mask = 0x8000000000000000LLU;
    while (!(mask & num)) mask >>= 1;
    return mask;
  }
}
于 2013-05-30T03:47:00.557 に答える
0

提案されたビットをいじるトリックの最悪の場合のパフォーマンスは、いくつかのビットを徐々に 1 にすることで改善できる/改善する必要がorあります。

 int s=1;
 while ((n+1) & n) {
    n|=n >> s;
    s<<=1;
 }
 return (n+1) >> 1;

このフラグメントは、すべての最下位ビットが 1 の場合に終了し、必要な log2(log2(n)) 反復だけです。

于 2013-05-30T04:19:34.767 に答える
0

再帰は一般に反復ほど効率的ではないことはわかっていますが、どうしようもありません-私は良い再帰が大好きです:

unsigned topBit(unsigned n) {
   unsigned m = n & (n-1);
   return m ? topBit(m) : n;
}

補遺: 実際のタイミングは、最適化してコンパイルした場合、@LaurenceGonsalves の反復バージョンよりもわずかに高速であることが示されました。

于 2013-05-30T19:01:45.753 に答える
0

これは、あなたのバージョンよりも約 2 倍高速です。

uint64_t g(uint64_t num) {
    uint64_t r = 1;
    num = num >> 1;
    while(num>r)   {
        r <<= 1;
    }
    return r;
}
于 2013-05-30T02:50:45.513 に答える