以128位整數計數前導零的數目

如何有效地計算128位整數中的前導零數（uint128_t）？以128位整數計數前導零的數目

我知道GCC的內置功能：

__builtin_clz，__builtin_clzl，__builtin_clzll
__builtin_ffs，__builtin_ffsl，__builtin_ffsll

但是，這些功能都只能在32位和64位工作整數。

我也發現了一些SSE指令：

__lzcnt16，，__lzcnt64

正如你可能已經猜到，有16只，這些工作，32位和64位整數。

128位整數是否有任何類似，高效的內置功能？

來源

2015-02-10 user1494080

我假設解決它爲兩個64位整數，然後結合，對亞來說太貴了？ – Yakk 2015-02-10 03:28:48

那麼，我必須這樣做，只要沒有人知道更好的解決方案。然而，單一指令可能會比整個換檔，鑄造，分支等更有效率，絕對更美麗。 – user1494080 2015-02-10 03:47:57

你可以通過將它包裝在一個函數中來隱藏醜陋。 – 2015-02-10 04:33:49

inline int clz_u128 (uint128_t u) { 
    uint64_t hi = u>>64; 
    uint64_t lo = u; 
    int retval[3]={ 
    __builtin_clzll(hi), 
    __builtin_clzll(lo)+64, 
    128 
    }; 
    int idx = !hi + ((!lo)&(!hi)); 
    return retval[idx]; 
}

這是一個分支免費的變種。請注意，比分支解決方案中完成的工作量更多，實際上分支可能是可預測的。

它也依賴於__builtin_clzll沒有崩潰時喂0：文檔說結果是未定義的，但它只是未指定或未定義？

來源

2015-02-10 14:14:48 Yakk

必須在'__builtin_clzll（lo）'後面添加'+ 64'，對吧？ ''__builtin_clsll（）'對所有輸入起作用的替代方案是'64 - __builtin_ffsll（）'。 – user1494080 2015-02-10 14:40:19

@ user1494080是的，哎呀。如果'__builtin_clzll'未定義只是「我輸出垃圾」，我們就可以。如果它是「我崩潰」，那就不好。我不知道他們是什麼意思的「未定義」;也許他們在某個地方定義了它的意思。 – Yakk 2015-02-10 14:47:11

我接受了這種方法，因爲在我的應用程序中比其他應用程序快了一點。 – user1494080 2015-02-10 23:47:24

假設一個'隨機'分佈，第一個非零位將會處於高位64位，並具有壓倒性的概率，因此首先測試一半是有意義的。

看一看生成的代碼爲：

/* inline */ int clz_u128 (uint128_t u) 
{ 
    unsigned long long hi, lo; /* (or uint64_t) */ 
    int b = 128; 

    if ((hi = u >> 64) != 0) { 
     b = __builtin_clzll(hi); 
    } 
    else if ((lo = u & ~0ULL) != 0) { 
     b = __builtin_clzll(lo) + 64; 
    } 

    return b; 
}

我希望GCC使用bsrq指令，以實現每個__builtin_clzll - 位掃描反向，即最顯著位的位置 - 連同一個xor ，(msb^63)或sub,(63 - msb)，將其變成領先的零計數。 gcc可能會生成lzcnt指令和正確的-march=（架構）選項。

編輯：其他人指出，「分配」是不是在這種情況下，相關的，因爲uint64_t中需要無論要測試的HI。

來源

2015-02-10 04:53:33

取決於隨機分佈。爲了在整個空間上均勻分佈，當然。對於其他人，也許不是。 – 2015-02-10 05:00:41

如何分岔！我會受到3大小數組查找解決方案的誘惑。但分支預測將會使上述速度更快。是的，除非這個值是一個隨機非理性的分數部分，否則統一隨機分佈的假設是有問題的。但是，即使沒有這個假設，你也需要測試非零高字節。試試吧。這個假設是一個紅鯡魚。 – Yakk 2015-02-10 12:45:06

@BrettHale分佈看起來並不明顯，但它不是一致的分佈。但是，我總是必須先測試高位，不是嗎？另一個問題：'＆〜0ULL'部分是否必要？縮小轉換不會自動截斷高位？ – user1494080 2015-02-10 13:24:22

只要海灣合作委員會支持 128位整數的目標，雅克的答案適用於各種目標。然而，注意，平臺X86-64，具有Intel處理器的Haswell或更新上，有一個更有效的解決方案：

#include <immintrin.h> 
#include <stdint.h> 
// tested with compiler options: gcc -O3 -Wall -m64 -mlzcnt 

inline int lzcnt_u128 (unsigned __int128 u) { 
    uint64_t hi = u>>64; 
    uint64_t lo = u; 
    lo = (hi == 0) ? lo : -1ULL; 
    return _lzcnt_u64(hi) + _lzcnt_u64(lo); 
}

的_lzcnt_u64固有編譯器（gcc 5.4）到lzcnt指令，這是公定義爲零輸入（它返回64），與gcc的__builtin_clzll（）相反。三元運算符編譯爲cmove指令。

來源

2016-11-10 13:23:15 wim

以128位整數計數前導零的數目

回答

相關問題