在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

Answer 2

您可以简单地计算在值为零之前必须删除位的次数:

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

Answer 3

The Cleanest and Quickest... （适用于 .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 的启发。
• 这也支持超过 32 位。我还没有测试过最大值，但至少达到了 2^38。
• 在生产代码上谨慎使用，因为这可能会在不是小端的架构上失败。

以下是一些基准测试：（此处的代码：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在另一篇文章中创建的那个。这个没有潜在的架构问题，它也支持零，同时保持与 SPWorley 的 float 方法几乎相同的性能。

2020 年 3 月 13 日更新： 史蒂夫注意到Log2_SunsetQuest3中存在一些遗漏的错误。

2020 年 4 月 26 日更新：添加了 phuclv指出的新 .Net Core 3 的 BitOperations.LeadingZeroCount() 。