9

2 の累乗であることがわかっている数値の 2 を底とする対数を取得するための最適なソリューションは何ですか ( 2^k)。(もちろん、私はそれ自体では2^kなく値だけを知っていkます。)

私が考えた 1 つの方法は、1 を減算してからビットカウントを行うことです。

lg2(n) = bitcount( n - 1 ) = k, iff k is an integer
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4

しかし、（キャッシュなしで）それを行うより速い方法はありますか？また、ビットカウントがそれほど速くないことを知っておくといいですか?

これは次のアプリケーションの 1 つです。

suppose you have bitmask
0b0110111000

and value
0b0101010101

and you are interested of
(value & bitmask) >> number of zeros in front of bitmask
(0b0101010101 & 0b0110111000) >> 3 = 0b100010

this can be done with

using bitcount
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1

or using lg2
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1 ) - 2

キャッシュなしでbitcountよりも高速であるためO(lg(k))にkは、ストレージ ビットのカウントよりも高速である必要があります。

4

4 に答える 4

6

はい。lg(n)問題の整数が 2 の累乗であることがわかっている場合は、のビット数なしでそれを行う方法を次に示します。

unsigned int x = ...;
static const unsigned int arr[] = {
  // Each element in this array alternates a number of 1s equal to
  // consecutive powers of two with an equal number of 0s.
  0xAAAAAAAA, // 0b10101010..         // one 1, then one 0, ...
  0xCCCCCCCC, // 0b11001100..         // two 1s, then two 0s, ...
  0xF0F0F0F0, // 0b11110000..         // four 1s, then four 0s, ...
  0xFF00FF00, // 0b1111111100000000.. // [The sequence continues.]
  0xFFFF0000
}

register unsigned int reg = (x & arr[0]) != 0;
reg |= ((x & arr[4]) != 0) << 4;
reg |= ((x & arr[3]) != 0) << 3;
reg |= ((x & arr[2]) != 0) << 2;
reg |= ((x & arr[1]) != 0) << 1;

// reg now has the value of lg(x).

各ステップで、 のビットのいずれかが の代替ビットマスクと共有されているreg |=かどうかを連続的にテストします。もしそうなら、それは がそのビットマスクにあるビットを持っていることを意味し、は交互ビットマスクの長さの対数です。たとえば、0xFF00FF00 は 8 個の 1 と 0 の交互シーケンスであるため、このビットマスクでは 3 (または) です。xarrlg(x)2^kregkklg(8)

基本的に、各reg |= ((x & arr[k]) ...ステップ (および初期割り当て)は、lg(x)ビットkが設定されているかどうかをテストします。もしそうなら、それをreg;に追加します。これらすべてのビットの合計は になりますlg(x)。

たくさんの魔法のように見えるので、例を試してみましょう。値 2,048 が 2 の何乗であるかを知りたいとします。

// x = 2048
//   = 1000 0000 0000

register unsigned int reg = (x & arr[0]) != 0;
// reg =       1000 0000 0000
         & ... 1010 1010 1010
       =       1000 0000 0000 != 0
// reg = 0x1 (1)        // <-- Matched! Add 2^0 to reg.

reg |= ((x & arr[4]) != 0) << 4;
// reg =     0x .. 0800
           & 0x .. 0000
       =              0 != 0
// reg = reg | (0 << 4) // <--- No match.
// reg = 0x1 | 0
// reg remains 0x1.

reg |= ((x & arr[3]) != 0) << 3;
// reg =     0x .. 0800
           & 0x .. FF00
       =            800 != 0
// reg = reg | (1 << 3) // <--- Matched! Add 2^3 to reg.
// reg = 0x1 | 0x8
// reg is now 0x9.         

reg |= ((x & arr[2]) != 0) << 2;
// reg =     0x .. 0800
           & 0x .. F0F0
       =              0 != 0
// reg = reg | (0 << 2) // <--- No match.
// reg = 0x9 | 0
// reg remains 0x9.        

reg |= ((x & arr[1]) != 0) << 1;
// reg =     0x .. 0800
           & 0x .. CCCC
       =            800 != 0
// reg = reg | (1 << 1) // <--- Matched! Add 2^1 to reg.
// reg = 0x9 | 0x2
// reg is now 0xb (11).

の最終値regは 2^0 + 2^1 + 2^3 であり、実際には 11 であることがわかります。

于 2010-02-06T17:48:40.863 に答える
5

数値が2の累乗であることがわかっている場合は、>>0になるまで右にシフト（）することができます。右にシフトした回数（マイナス1）はあなたのkです。

編集：これよりも高速なルックアップテーブルメソッドです（ただし、スペースをいくらか犠牲にしますが、1トンは犠牲にしません）。http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/を参照してください。

于 2010-02-06T16:57:25.837 に答える
3

多くのアーキテクチャには、「最初のものを見つける」命令 (bsr、clz、bfffo、cntlzw など) があり、ビットカウント アプローチよりもはるかに高速です。

于 2010-02-06T17:47:23.890 に答える
-2

フロートを処理してもかまわない場合は、 を使用できますlog(x) / log(2)。

于 2010-02-06T17:09:04.923 に答える