Fastest way to get last significant bit position in a ulong (C#)?

Question

What is the fastest(or at least very fast) way to get first set(1) bit position from least significant bit (LSB) to the most significant bit (MSB) in a ulong (C#)? For ulong i = 18; (10010) that would be 2(or 1 if we are counting position from 0).

MS C++ compiler has _BitScanForward64 Intrinsics for this task, but C# compiler doesn't have analogue.

Can you point to something that defines "last significant bit position" as you mean it? Are you referring to the "2" position (next to last bit) because it has a value of 1, but for 10011 the last significant bit would be 1, and for 10100 it would be 4? — Scott Hannen, May 07 '16 at 01:12
This solution is written in C++, but it should be adaptable to C# and is only a couple of operations: http://stackoverflow.com/a/757266/116614. Also see http://stackoverflow.com/q/31374628/116614 — mellamokb, May 07 '16 at 01:36
[This is the fastest way](https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx). Takes one cpu cycle, can't make it faster than that. Everything is possible, nothing is simple. — Hans Passant, May 07 '16 at 08:58
@HansPassant yes, thank you.. I know about C++ _BitScanReverse. Unfortunataly C# compiler doesn't provide such intrinsics AFAIK. — Brans Ds, May 07 '16 at 12:38

Petter T · Answer 1 · 2021-05-25T09:18:49.953

6

With .NET Core 3.0 introducing hardware intrinsics, the fastest solution should be

ulong value = 18;
ulong result = System.Runtime.Intrinsics.X86.Bmi1.X64.TrailingZeroCount(value);

Alternatively, the new System.Numerics.Bitoperations methods also use hardware intrinsics:

int result2 = System.Numerics.BitOperations.TrailingZeroCount(value);

edited May 25 '21 at 09:18

answered Jun 18 '20 at 12:24

Petter T

3,387
2
19
31

Antonín Lejsek · Answer 2 · 2016-05-07T19:02:26.720

public static UInt64 CountTrailingZeros(UInt64 input)
{
    if (input == 0) return 64;

    UInt64 n = 0;

    if ((input & 0xFFFFFFFF) == 0) { n = 32; input = input >> 32; }
    if ((input & 0xFFFF) == 0) { n = n + 16; input = input >> 16; }
    if ((input & 0xFF) == 0) { n = n + 8; input = input >> 8; }
    if ((input & 0xF) == 0) { n = n + 4; input = input >> 4; }
    if ((input & 3) == 0) { n = n + 2; input = input >> 2; }
    if ((input & 1) == 0) { ++n; }

    return n;
}

I changed the answer of Michael D. O'Connor to match Your question.

Brans Ds · Accepted Answer · 2016-05-09T11:48:19.877

I have measured perfomance of all answers.

The winner is not present here classic De Bruijn sequence approach.

    private const ulong DeBruijnSequence = 0x37E84A99DAE458F;

    private static readonly int[] MultiplyDeBruijnBitPosition =
    {
        0, 1, 17, 2, 18, 50, 3, 57,
        47, 19, 22, 51, 29, 4, 33, 58,
        15, 48, 20, 27, 25, 23, 52, 41,
        54, 30, 38, 5, 43, 34, 59, 8,
        63, 16, 49, 56, 46, 21, 28, 32,
        14, 26, 24, 40, 53, 37, 42, 7,
        62, 55, 45, 31, 13, 39, 36, 6,
        61, 44, 12, 35, 60, 11, 10, 9,
    };

    /// <summary>
    /// Search the mask data from least significant bit (LSB) to the most significant bit (MSB) for a set bit (1)
    /// using De Bruijn sequence approach. Warning: Will return zero for b = 0.
    /// </summary>
    /// <param name="b">Target number.</param>
    /// <returns>Zero-based position of LSB (from right to left).</returns>
    private static int BitScanForward(ulong b)
    {
        Debug.Assert(b > 0, "Target number should not be zero");
        return MultiplyDeBruijnBitPosition[((ulong)((long)b & -(long)b) * DeBruijnSequence) >> 58];
    }

The fastest way is to inject Bit Scan Forward (bsf) Bit Instruction to assembly after JIT compiler instead of BitScanForward body, but this requires much more efforts.

Would you have any URLs to recommend illustrating how one could inject the BSF instruction instead of the body? I understand this is a tricky thing to do, but the performance advantages may overcome the development cost associated to it. — OBones, Feb 21 '20 at 15:39
Performance tested this myself and can confirm that this is almost 2x faster than the other solutions offered — AidanH, Feb 26 '20 at 18:39
this answer and all comments here are before the 2020 answer using intrinsics. I suspect that would win. — Merlyn Morgan-Graham, Jun 21 '22 at 18:03

score 2 · Answer 4 · edited May 23 '17 at 12:16

2

public static UInt64 CountLeadingZeros(UInt64 input)
{
    if (input == 0) return 64;

    UInt64 n = 1;

    if ((input >> 32) == 0) { n = n + 32; input = input << 32; }
    if ((input >> 48) == 0) { n = n + 16; input = input << 16; }
    if ((input >> 56) == 0) { n = n + 8; input = input << 8; }
    if ((input >> 60) == 0) { n = n + 4; input = input << 4; }
    if ((input >> 62) == 0) { n = n + 2; input = input << 2; }
    n = n - (input >> 63);

    return n;
}

I'll bet this'll be faster. From here.

edited May 23 '17 at 12:16

Community

1
1

answered May 07 '16 at 02:18

Michael D. O'Connor

235
3
13

That is opposite operation for ulong i = 18 it returns 59, not 2 as expected. – Brans Ds May 07 '16 at 07:27

score 2 · Answer 5 · answered May 07 '16 at 22:15

static Int32 GetLSBPosition(UInt64 v) {
    UInt64 x = 1;
    for (var y = 0; y < 64; y++) {
        if ((x & v) == x) {
            return y;
        }
        x = x << 1;
    }
    return 0;
}

While similar to Alexander's answer, this form performs consistently faster, about 46 million operations per second on my machine.

Also, I have written it to be Zero based, but personally I think it should be 1 based, eg:

Assert.Equal(0, GetLSBPosition(0));
Assert.Equal(1, GetLSBPosition(1));
Assert.Equal(1, GetLSBPosition(3));

If you did decide you wanted it 1 based, change the for loop to `for (var y = 1; y <= 64; y++)` — Doug Wilson, May 07 '16 at 22:32

score 1 · Answer 6 · answered May 08 '16 at 23:01

1

As a bit-wise operation, the lowest set bit is:

ulong bit = x & ~(x-1);

and the original value with the lowest on-bit set to off is:

x & (x-1)

So to get all the bits that are on:

public static void Main()
{
    ulong x = 13;
    while(x > 0)
    {
        ulong bit = x & ~(x-1);
        x = x & (x-1);

        Console.WriteLine("bit-value {0} is set", bit);
    }
}

Output

bit-value 1 is set
bit-value 4 is set
bit-value 8 is set

answered May 08 '16 at 23:01

abelenky

63,815
23
109
159

While this doesn't return the bit position, I still like the algorithm! – v01pe Nov 29 '21 at 14:55

Alexander Petrov · Answer 7 · 2016-05-08T22:50:33.103

-1

The solution with a very fast bit operations. Only unsafe code can be faster.

ulong n = 18; // 10010
ulong b = 1;
int p = 0;

for (int i = 0; i < 64; i++)
{
    if ((n & b) == b)
    {
        p = i;
        break;
    }
    b = b << 1;
}

Console.WriteLine(p);

edited May 08 '16 at 22:50

answered May 07 '16 at 11:41

Alexander Petrov

13,457
2
20
49

1

I disagree that only unsafe code can be faster. Your loop runs through each bit-position, one by one. See my answer for a solution that skips directly to only the bits that are set. – abelenky May 08 '16 at 23:14

Fastest way to get last significant bit position in a ulong (C#)?

7 Answers7