与2 ^ n相反

Question

对于任何b,可以快速计算函数a = 2 ^ b a = 1 << b.那么反过来说,为任何给定的a获得b的值？它应该相对较快,因此日志是不可能的.任何不是O(1)的东西也都很糟糕.

我很高兴能不能做到,如果它根本不可能太没有记录或搜索类的事情.

Answer 1

建立一个查找表.对于32位整数,只有32个条目,因此它是O(1).

大多数体系结构还有一条指令来查找数字a的最高位的位置,即值b.(gcc提供了这个__builtin_clz功能.)

对于BigInt,可以通过重复除以2来计算O(log a).

int b = -1;
while (a != 0) {
  a >>= 1;
  ++ b;
}

Answer 2

对于这种事情,我通常会在这个页面上引用一些黑客攻击:

• 比特扭曲黑客

例如:

使用查找表查找整数的日志库2:

static const char LogTable256[256] = 
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

该页面上还有一些O(log(n))算法.