找到64位整數中最大和最小有效位的快速方法

在StackOverflow上有很多這方面的問題。很多。但是我不能找到答案是：找到64位整數中最大和最小有效位的快速方法

工程在C＃
Works的64位整數（而不是32位）

更快比：

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

或甚至

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

我是assu在此處提供64位Intel CPU。

一個有用的參考是Bit Hacks page和另一個是fxtbook.pdf 但是，雖然這些提供了有用的方向來解決這個問題，但他們沒有給出現成的答案。

我在使用可重複使用的功能後，只能爲C＃執行類似於_BitScanForward64和_BitScanReverse64的操作。

來源

2015-07-13 Andrew Savinykh

這是不是基本上相同http://stackoverflow.com/questions/10439242/count-leading-zeroes-in-an-int32？顯然，你必須將它調整爲64位，它會給你與你正在尋找的號碼相反的信息，但它表達了相同的信息。 – Taekahn

@Taekahn調整到64位並不是微不足道的。嘗試一下。正如我在問題中所承認的那樣，32位答案確實存在於SO上。 –

根據我的評論，這是C＃中的一個函數，用於計算爲64位整數修改的前導零位。

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

來源

2015-07-13 07:24:34 Taekahn

根據我的性能測試，這比我的輸入速度快。幹得好，謝謝！ –

謝謝。沒問題。 – Taekahn

如果可以，我很好奇你會用它做什麼？盡我所能，我想不出任何實際的應用。 – Taekahn

這樣做的其中一種方式是在問題鏈接的Bit Hacks頁面上描述，它利用了De Bruijn sequence。不幸的是，這個頁面並沒有給出所述序列的64位版本。 This useful page解釋瞭如何構建De Bruijn序列，以及this one給出了用C++編寫的序列生成器的例子。如果我們適應給定的代碼，我們可以生成多個序列，其中一個在下面的C＃代碼給出：

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

我也貼了序列發生器的我的C＃端口github

另一個相關的文章沒有在De Bruijn序列的體面封面的問題中提到，可以找到here。

來源

2015-07-13 02:24:16

找到64位整數中最大和最小有效位的快速方法

回答

相關問題