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

Question

如何才能最有效地计算C#中整数(以2为底的对数)所需的位数？例如：

int bits = 1 + log2(100);

=> bits == 7

Answer 1

最干净最快...(适用于.Net core 3.1及更高版本，并从.Net 5.0开始领先性能)

int val = BitOperations.Log2(x);

亚军...(在.Net 5以下的版本中速度最快，在.Net 5中排名第二)

int val = (int)((BitConverter.DoubleToInt64Bits(x) >> 52) + 1) & 0xFF;

备注：

受SPWorley 3/22/2009.

• This启发，在浮点数中使用指数的想法也支持超过32位。
• 我还没有测试最大值，但至少测试了2^38。在生产代码上使用
• 时要小心，因为这可能会在非little-endianness.

的体系结构上失败

以下是一些基准测试：(代码在这里：https://github.com/SunsetQuest/Fast-Integer-Log2)

                                      1-2^32                  32-Bit  Zero 
Function                Time1 Time2 Time3 Time4 Time5 Errors Support Support 
Log2_SunsetQuest3       18     18    79167  19    18    255      N       N
Log2_SunsetQuest4       18     18    86976  19    18      0      Y       N
LeadingZeroCountSunsetq -      -        -   30    20      0      Y       Y
Log2_SPWorley           18     18    90976  32    18   4096      N       Y
MostSigBit_spender      20     19    86083  89    87      0      Y       Y
Log2_HarrySvensson      26     29    93592  34    31      0      Y       Y
Log2_WiegleyJ           27     23    95347  38    32      0      Y       N
Leading0Count_phuclv     -      -        -  33    20    10M      N       N
Log2_SunsetQuest1       31     28    78385  39    30      0      Y       Y
HighestBitUnrolled_Kaz  33     33   284112  35    38   2.5M      N       Y
Log2_Flynn1179          58     52    96381  48    53      0      Y       Y
BitOperationsLog2Sunsetq -      -        -  49    15      0      Y       Y
GetMsb_user3177100      58     53   100932  60    59      0      Y       Y
Log2_Papayaved         125     60   119161  90    82      0      Y       Y
FloorLog2_SN17         102     43   121708  97    92      0      Y       Y
Log2_DanielSig          28     24   960357  102  105     2M      N       Y
FloorLog2_Matthew_Watso 29     25    94222  104  102      0      Y       Y
Log2_SunsetQuest2      118    140   163483  184  159      0      Y       Y
Msb_version            136    118  1631797  212  207      0      Y       Y
Log2_SunsetQuest0      206    202   128695  212  205      0      Y       Y
BitScanReverse2        228    240  1132340  215  199     2M      N       Y
Log2floor_version       89    101 2 x 10^7  263  186      0      Y       Y
UsingStrings_version  2346   1494 2 x 10^7 2079 2122      0      Y       Y
                                                                           
Zero_Support = Supports Zero if the result is 0 or less
Full-32-Bit  = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf on small numbers)
Time3 = time to run entire 1-2^32 in sequence using Parallel.For. Most results range will on the larger end like 30/31 log2 results. (note: because random was not used some compiler optimization might have been applied so this result might not be accurate) 
Time4 = .Net Core 3.1
Time5 = .Net 5

基准测试说明： AMD Ryzen CPU，发布模式，不附加调试器，.net core 3.1

我真的很喜欢spender in another post创建的那个。这个方法没有潜在的架构问题，它还支持零，同时保持了与SPWorley的float方法几乎相同的性能。

2020年3月13日更新： Steve noticed说Log2_SunsetQuest3中有一些错误被遗漏了。

更新4/26/2020:添加了新的.Net核心3的BitOperations.LeadingZeroCount()作为pointed out by phuclv。

Answer 2

对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;
}

此外，还应添加对Log的检查，因为上面的结果将产生0，并且n==0 (0)是未定义的(与基数无关)。

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

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

变为(设R0 = n，R1 =位)

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

Answer 3

您可以简单地计算需要删除多少次位，直到该值为零：

int bits = 0;
while (n > 0) {
  bits++;
  n >>= 1;
}

对于较大的数字，更有效的方法是先计算位组：

int bits = 0;
while (n > 255) {
  bits += 8;
  n >>= 8;
}
while (n > 0) {
  bits++;
  n >>= 1;
}

编辑：

最有效的方法是使用Flynn1179建议的二进制步骤(灵感:)，但将循环扩展为硬编码检查。这至少比上面的方法快两倍，但也有更多的代码：

int bits = 0;
if (n > 32767) {
  n >>= 16;
  bits += 16;
}
if (n > 127) {
  n >>= 8;
  bits += 8;
}
if (n > 7) {
  n >>= 4;
  bits += 4;
}
if (n > 1) {
  n >>= 2;
  bits += 2;
}
if (n > 0) {
  bits++;
}