Najszybszy sposób uzyskania ostatniej znaczącej pozycji bitu w ulongu (C#)?

Question

Jaki jest najszybszy (a przynajmniej bardzo szybki) sposób na uzyskanie pierwszego zestawu (1) pozycji bitowej od najmniej znaczącego bitu (LSB) do najbardziej znaczącego bitu (MSB) w ulongu (C#)? Dla ulong i = 18;(10010) które byłyby 2 (lub 1, jeśli liczymy pozycję od 0).

Kompilator MS C++ ma _BitScanForward64 Zasadnicze dla tego zadania, ale kompilator C# nie ma analogowy.

Answer 1

mam zmierzyć osiągów wszystkich odpowiedzi.

Zwycięzca nie ma tutaj klasycznego podejścia do sekwencji De Bruijn.

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]; 
    } 

Najszybszym sposobem jest wstrzyknięcie Bit Skanuj do przodu (BSF) Bit instrukcja do montażu po kompilator JIT zamiast BitScanForward ciała, ale to wymaga dużo więcej wysiłku.

Answer 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; 
} 

założę to będzie szybciej. Od here.

Answer 3

Rozwiązanie z bardzo szybkimi operacjami bitowymi. Tylko niebezpieczny kod może być szybszy.

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); 

Answer 4

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; 
} 

Zmieniłem odpowiedź Michael D. O'Connor pasujące do Twojego pytania.

Answer 5

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; 
} 

Chociaż podobna do odpowiedzi Aleksandra, ta forma wykonuje konsekwentnie szybciej, około 46 milionów operacji na sekundę na moim komputerze.

Również Pisałem ją za Zero opiera, ale osobiście myślę, że powinno być 1 na podstawie np:

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

Answer 6

jako operacja bitową, najniższy zestaw bit jest:

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

i oryginalna wartość z najniższych na bit jest ustawiony na oFF:

x & (x-1) 

Tak, aby uzyskać wszystkie bity, które są na:

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); 
    } 
} 

Wyjście

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