Un modo rapido per trovare il bit più significativo e meno significativo in un numero intero a 64 bit

Ci sono molte domande su StackOverflow. Molto. Tuttavia non riesco a trovare una risposta che:Un modo rapido per trovare il bit più significativo e meno significativo in un numero intero a 64 bit

Lavori in C#
Opere per interi a 64 bit (in contrapposizione a 32-bit)

Più veloce di:

private static int Obvious(ulong v) 
{ 
    int r = 0; 
    while ((v >>= 1) != 0) 
    { 
     r++; 
    } 
    return r; 
}

O anche

int r = (int)(Math.Log(v,2));

Sono assu qui una CPU Intel a 64 bit.

Un riferimento utile è il Bit Hacks page e un altro è fxtbook.pdf Tuttavia, mentre questi forniscono indicazioni utili per affrontare il problema, non forniscono una risposta pronta.

Sono dopo una funzione riutilizzabile che può fare qualcosa di simile a _BitScanForward64 e _BitScanReverse64 solo per C#.

fonte

2015-07-13 Andrew Savinykh

Non è essenzialmente lo stesso di http://stackoverflow.com/questions/10439242/count-leading-zeroes-in-an-int32? Ovviamente, dovresti regolarlo per 64 bit, e ti dà l'opposto del numero che stai cercando, ma trasmette le stesse informazioni. – Taekahn

@Taekahn la regolazione a 64 bit non è affatto banale. Provalo. Come ho riconosciuto nella domanda, la risposta a 32 bit esiste su SO. –

Come per il mio commento, questa è una funzione in C# per contare i primi zero bit modificati per un intero a 64 bit.

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

fonte

2015-07-13 07:24:34 Taekahn

Secondo i miei test delle prestazioni, questo è più veloce del mio, al mio ingresso. Ben fatto, grazie! –

Grazie. Nessun problema. – Taekahn

Se posso permettermi, sono curioso di sapere a cosa vorresti usare? Prova come potrei, non riesco a pensare ad alcuna applicazione pratica per questo. – Taekahn

Uno dei modi per farlo, descritto nella pagina Bit Hacks collegata nella domanda, è l'utilizzo di De Bruijn sequence. Sfortunatamente questa pagina non fornisce una versione a 64 bit di detta sequenza. This useful page spiega come è possibile costruire sequenze De Bruijn e this one fornisce un esempio del generatore di sequenze scritto in C++. Se adattiamo il codice dato possiamo generato più sequenze, uno dei quali figura in C# codice qui sotto:

public static class BitScanner 
{ 
    private const ulong Magic = 0x37E84A99DAE458F; 

    private static readonly int[] MagicTable = 
    { 
     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, 
    }; 

    public static int BitScanForward(ulong b) 
    { 
     return MagicTable[((ulong) ((long) b & -(long) b)*Magic) >> 58]; 
    } 

    public static int BitScanReverse(ulong b) 
    { 
     b |= b >> 1; 
     b |= b >> 2; 
     b |= b >> 4; 
     b |= b >> 8; 
     b |= b >> 16; 
     b |= b >> 32; 
     b = b & ~(b >> 1); 
     return MagicTable[b*Magic >> 58]; 
    } 
}

Ho anche inviato il mio C# porta del generatore di sequenza di github

Un altro articolo correlato non menzionato nella domanda con una discreta copertura delle sequenze di De Bruijn, può essere trovato here.

fonte

2015-07-13 02:24:16

Un modo rapido per trovare il bit più significativo e meno significativo in un numero intero a 64 bit

risposta

Problemi correlati