在 C# 中计算整数的 log2 的最快方法是什么? [英] What's the quickest way to compute log2 of an integer in C#?
问题描述
如何最有效地计算 C# 中整数(以对数为 2)所需的位数?例如:
How can I most efficiently count the number of bits required by an integer (log base 2) in C#? For example:
int bits = 1 + log2(100);
=> bits == 7
推荐答案
The Cleanest and Quickest...(适用于 .Net core 3.1 及更高版本，并从 .Net 5.0 开始性能领先)
The Cleanest and Quickest... (works in .Net core 3.1 and up and takes the performance lead starting in .Net 5.0)
int val = BitOperations.Log2(x);
亚军...(在 .Net 5 以下版本中最快，在 .Net 5 中排名第二)
Runner up... (fastest in versions below .Net 5, 2nd place in .Net 5)
int val = (int)((BitConverter.DoubleToInt64Bits(x) >> 52) + 1) & 0xFF;
注意事项:
- 在浮点中使用指数的想法的灵感来自 SPWorley2009 年 3 月 22 日.
- 这也支持超过 32 位.我还没有测试过最大值，但至少达到了 2^38.
- 在生产代码上谨慎使用，因为这可能会在非小端的架构上失败.
以下是一些基准测试:(此处的代码:https://github.com/SunsetQuest/Fast-Integer-Log2)
Here are some benchmarks: (code here: 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
Benchmark notes: AMD Ryzen CPU, Release mode, no-debugger attached, .net core 3.1
我真的很喜欢另一篇文章中的spender创建的那个.这个没有潜在的架构问题，它也支持零，同时保持与来自 SPWorley 的 float 方法几乎相同的性能.
I really like the one created by spender in another post. This one does not have the potential architecture issue and it also supports Zero while maintaining almost the same performance as the float method from SPWorley.
2020 年 3 月 13 日更新: Steve注意到 Log2_SunsetQuest3 中存在一些被遗漏的错误.
Update 3/13/2020: Steve noticed that there were some errors in Log2_SunsetQuest3 that were missed.
2020 年 4 月 26 日更新:添加了新的 .Net Core 3 的 BitOperations.LeadingZeroCount() 作为 指出由 phuclv 输出.
Update 4/26/2020: Added new .Net Core 3's BitOperations.LeadingZeroCount() as pointed out by phuclv.
这篇关于在 C# 中计算整数的 log2 的最快方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
