如何最有效地计算C#中整数(对数为2)所需的位数?例如:
int bits = 1 + log2(100); => bits == 7
最干净的… (适用于.net core 3.0及更高版本…)
int val = BitOperations.Log2(x);
最快的…
[StructLayout(LayoutKind.Explicit)] private struct ConverterStruct2 { [FieldOffset(0)] public ulong asLong; [FieldOffset(0)] public double asDouble; } [MethodImpl(MethodImplOptions.NoInlining)] public static int Log2(uint oval) //SunsetQuest4 version { ConverterStruct2 a; a.asLong = 0; a.asDouble = val; return (int)((a.asLong >> 52) + 1) & 0xFF; }
笔记:
这里是一些基准:(代码在这里:https : //github.com/SunsetQuest/Fast-Integer- Log2)
1-2^32 32-Bit Zero Function Time1 Time2 Time3 Time4 Errors Support Support Log2_SunsetQuest3 18 18 79167 19 255 N N Log2_SunsetQuest4 18 18 86976 19 0 Y N LeadingZeroCount_Sunsetq - - - 30 0 Y Y Log2_SPWorley 18 18 90976 32 4096 N Y MostSigBit_spender 20 19 86083 89 0 Y Y Log2_HarrySvensson 26 29 93592 34 0 Y Y Log2_WiegleyJ 27 23 95347 38 0 Y N Leading0Count_phuclv - - - 33 10M N N Log2_SunsetQuest1 31 28 78385 39 0 Y Y HighestBitUnrolled_Kaz 33 33 284112 35 2.5M N Y Log2_Flynn1179 58 52 96381 48 0 Y Y BitOperationsLog2Sunsetq - - - 49 0 Y Y GetMsb_user3177100 58 53 100932 60 0 Y Y Log2_Papayaved 125 60 119161 90 0 Y Y FloorLog2_SN17 102 43 121708 97 0 Y Y Log2_DanielSig 28 24 960357 102 2M N Y FloorLog2_Matthew_Watson 29 25 94222 104 0 Y Y Log2_SunsetQuest2 118 140 163483 184 0 Y Y Msb_Protagonist 136 118 1631797 212 0 Y Y Log2_SunsetQuest0 206 202 128695 212 0 Y Y BitScanReverse2 228 240 1132340 215 2M N Y Log2floor_greggo 89 101 2x10^7 263 0 Y Y UsingStrings_Rob 2346 1494 2x10^7 2079 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
基准测试说明: AMD Ryzen CPU,Release模式,未调试器连接,.net core 3.1
我真的很喜欢花钱在另一个帖子中创建的那个。这没有潜在的体系结构问题,它还支持零,同时保持与SPWorley的float方法几乎相同的性能。
2020年3月13日更新: 史蒂夫注意到 Log2_SunsetQuest3中缺少一些错误。