algorithm - 2 ^ n 的相反数

Question

通过执行 a = 1 << b 可以快速计算出任意 b 的函数 a = 2 ^ b .反过来，对于任何给定的 a 获取 b 的值呢？它应该比较快，所以日志是不可能的。任何不是 O(1) 的东西也是不好的。

如果没有日志或搜索类型的东西根本不可能完成，我也很高兴无法完成。

Answer 1

建立一个查找表。对于 32 位整数，只有 32 个条目，所以它是 O(1)。

大多数体系结构还有一条指令，用于查找数字a 的最高有效位的位置，即值b。 (gcc 为此提供了 __builtin_clz function。)

对于 BigInt，可以通过重复除以 2 在 O(log a) 中计算。

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