Hacker News new | ask | show | jobs
by 0xcoffee 530 days ago
C# Version:

    private static uint FastDigitCount(ulong value)
    {
        ReadOnlySpan<byte> digitCounts = [19, 19, 19, 19, 18, 18, 18, 17, 17, 17, 16, 16, 16, 16, 15, 15, 15, 14, 14, 14, 13, 13, 13, 13, 12, 12, 12, 11, 11, 11, 10, 10, 10, 10, 9, 9, 9, 8, 8, 8, 7, 7, 7, 7, 6, 6, 6, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1];
        ReadOnlySpan<ulong> digitCountThresholds = [0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 9999999999, 99999999999, 999999999999, 9999999999999, 99999999999999, 999999999999999, 9999999999999999, 99999999999999999, 999999999999999999, 9999999999999999999];
    
        var leadingZeros = BitOperations.LeadingZeroCount(value);
        var originalDigitCount = digitCounts[leadingZeros];
        return originalDigitCount + (value > digitCountThresholds[originalDigitCount] ? 1u : 0u);
    }
Benchmark: https://stackoverflow.com/a/79337820/4503491