c# - 在 C# 中计算整数 log2 的最快方法是什么？

Question

如何最有效地计算 C# 中整数(对数基数 2)所需的位数？例如:

int bits = 1 + log2(100);

=> bits == 7

Answer 1

轻微 对 Guffa 答案的改进...由于您添加到结果中的数量始终是 2 的幂，因此使用位操作可以在某些体系结构上产生轻微的改进。此外，由于我们的上下文是位模式，因此使用十六进制更易读。在这种情况下，将算术移动 2 的幂是有用的。

int bits = 0;

if (n > 0xffff) {
  n >>= 16;
  bits = 0x10;
}

if (n > 0xff) {
  n >>= 8;
  bits |= 0x8;
}

if (n > 0xf) {
  n >>= 4;
  bits |= 0x4;
}

if (n > 0x3) {
  n >>= 2;
  bits |= 0x2;
}

if (n > 0x1) {
  bits |= 0x1;
}

还应添加对 n==0 的检查，因为以上将产生 0 的结果并且 Log(0) 未定义(无论基数如何)。

在 ARM 汇编中，该算法生成非常紧凑的代码，因为可以使用条件指令消除比较后的分支，从而避免流水线刷新。例如:

if (n > 0xff) {
   n >>= 8;
   bits |= 0x8;
}

变成(令 R0 = n，R1 = 位)

CMP R0, $0xff
MOVHI R0, R0, LSR $8
ORRHI R1, R1, $0x8