一尘不染

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

algorithm

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

int bits = 1 + log2(100);

=> bits == 7

阅读 445

收藏
2020-07-28

共1个答案

一尘不染

最干净的… (适用于.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;
    }

笔记:

  • 在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 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中缺少一些错误。

2020-07-28