如何得到一个2^k数的lg2值

Question

如何得到一个2^k数的lg2值

performancebit-manipulationmicro-optimizationlogarithmbitcount

9

如何获取已知为2的幂次方（2^k）的数字的底数为2的对数？（当然，我只知道值为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是存储位的数量。

- Egon

4个回答

5

如果您知道一个数字是2的幂，那么可以将其向右移位(>>)直到等于0。向右移位的次数(减1)就是k。

编辑：比这更快的方法是查找表方法(虽然会牺牲一些空间，但不是很多)。请参见http://doctorinterview.com/index.html/algorithmscoding/find-the-integer-log-base-2-of-an-integer/。

- danben

你必须设置 k = #shifted - 1; - tur1ng

这种方法比位计数法慢。您可以使用O(lg(k))的位计数法，而这种移位在最坏情况下是O(k)。(k是存储位数的计数) - Egon

@egon - 我唯一看到的比lg k更好的是查找表方法。回答已更新。 - danben

@danben - 是的，感觉是这样...也许有人有一个很好的想法如何改进它。感觉通过利用数字是2的幂的事实来加速可能会更快。它只有k种状态需要考虑，这并不多。 - Egon

实际上，我在文章中找到了解决方案。如果值是2的幂，则方法3、4有版本。方法3有一个比使用位计数更快的版本。 - Egon

3

许多架构都有“查找第一个”指令（bsr、clz、bfffo、cntlzw等），这比位计数方法快得多。

- user149341

可能是最快的方式...... - Egon

-2

如果您不介意处理浮点数，可以使用 log(x) / log(2)。

- Ignacio Vazquez-Abrams

在大多数CPU上，这将需要数百个时钟周期。如果您有clz或类似的指令，可以在一个周期内完成。 - Paul R

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Feminella · Accepted Answer

是的。如果您知道所涉及的整数是2的幂，则可以在不使用lg(n)中的位计数的情况下执行此操作。

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).

我们可以看到，reg 的最终值是 2^0 + 2^1 + 2^3，也就是说它的值为 11。