9

获得以 2 为底的对数的最佳解决方案是什么，我知道是 2 的幂 ( 2^k)。（当然我只知道值2^k而不知道k它本身。）

我想到的一种方法是减去 1，然后进行位计数：

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

但是有没有更快的方法（没有缓存）？还有一些不涉及比特计数的东西会很高兴知道吗？

应用程序之一是：

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 的幂，那么这是一种无需 in 中的位计数的方法。

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 |=步骤中，我们依次测试以查看是否有任何位x与 中的交替位掩码共享arr。如果是，则意味着该lg(x)位掩码中有位，我们有效地添加2^k到reg，其中k是交替位掩码长度的对数。例如，0xFF00FF00 是 8 个 1 和 0 的交替序列，因此该位掩码k为 3（或lg(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).

我们看到 的最终值为reg2^0 + 2^1 + 2^3，确实是 11。

于 2010-02-06T17:48:40.863 回答
5

如果你知道这个数字是 2 的幂，你可以把它右移 ( >>) 直到它等于 0。你右移的次数（减 1）就是你的k.

编辑：比这更快的是查找表方法（虽然你牺牲了一些空间，但不是很多）。请参阅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 回答