64位整數二進制掃描：尋找首個 1 的高效算法與實現

編輯：關於C語言

前言：位掃描的實際需求

在系統編程、編碼壓縮、圖形處理等領域，經常需要快速定位一個整數二進制表示中「第一個 1」所在的位置（即最低有效位索引，BSF；或最高有效位索引，BSR）。以十進制 100 為例，其二進制為 1100100，最低位的 1 在索引 2（BSF），最高位的 1 在索引 6（BSR）。由於僅用於狀態標記，兩種方向均可接受。

方案一：內聯匯編 —— 直擊硬體指令

最直接的想法是利用 CPU 專用指令（x86 的 bsf/bsr）。但匯編移植性差，不同架構指令集不同，性能表現也不一。以下為 GCC AT&T 風格匯編實現 64 位 BSF：

inline int bsf_asm (uint64_t w)
{
    int x1, x2;
    asm ("bsf %0,%0\n"
         "jnz 1f\n"
         "bsf %1,%0\n"
         "jz 1f\n"
         "addl $32,%0\n"
         "1:"
       : "=&q" (x1), "=&q" (x2)
       : "1" ((int) (w >> 32)), "0" ((int) w));
    return x1;
}

同理，BSR 匯編實現：

inline int bsr_asm (uint64_t w)
{
    int x1, x2;
    asm ("bsr %1,%0\n"
         "jnz 1f\n"
         "bsr %0,%0\n"
         "subl $32,%0\n"
         "1: addl $32,%0"
       : "=&q" (x1), "=&q" (x2)
       : "1" ((int) (w >> 32)), "0" ((int) w));
    return x1;
}

方案二：純 C 實現 —— 可移植、無分支查表法

若不依賴特定指令集，可用「折疊 + 德布魯因序列」查表實現 O(1) BSF：

inline int bsf_folded (uint64_t bb)
{
    static const int lsb_64_table[64] = {
        63, 30,  3, 32, 59, 14, 11, 33,
        60, 24, 50,  9, 55, 19, 21, 34,
        61, 29,  2, 53, 51, 23, 41, 18,
        56, 28,  1, 43, 46, 27,  0, 35,
        62, 31, 58,  4,  5, 49, 54,  6,
        15, 52, 12, 40,  7, 42, 45, 16,
        25, 57, 48, 13, 10, 39,  8, 44,
        20, 47, 38, 22, 17, 37, 36, 26
    };
    unsigned int folded;
    bb ^= bb - 1;                 // 只保留最低位的 1
    folded = (int) bb ^ (bb >> 32); // 高低 32 位折疊
    return lsb_64_table[folded * 0x78291ACF >> 26]; // 德布魯因乘法哈希
}

核心技巧：bb ^= bb - 1 將最低位 1 及其右側所有位置 1，折疊後通過魔數 0x78291ACF 乘法映射到 6 位索引，查表得結果。

方案三：BSR 的分治查表法

BSR 可用「分治 + 256 字節查表」實現，遞歸深度固定為 log₂(32)=5：

inline int bsr32(uint32_t bb)
{
    static const char msb_256_table[256] = {
        0,0,1,1,2,2,2,2, 3,3,3,3,3,3,3,3,
        4,4,4,4,4,4,4,4, 4,4,4,4,4,4,4,4,
        5,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5,
        6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6,
        6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6,
        7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7
    };
    int result = 0;
    if (bb > 0xFFFF) { bb >>= 16; result += 16; }
    if (bb > 0xFF)   { bb >>= 8;  result += 8;  }
    return result + msb_256_table[bb];
}

inline int bsr_in_C(uint64_t bb)
{
    const uint32_t hb = bb >> 32;
    return hb ? 32 + bsr32((uint32_t)hb) : bsr32((uint32_t)bb);
}

方案四：浮點數指數位提取法（另類思路）

利用 IEEE 754 雙精度浮點數的指數位域直接獲取最高位索引：

inline int bsr_double (uint64_t bb)
{
    union {
        double d;
        struct {
            unsigned int mantissal : 32;
            unsigned int mantissah : 20;
            unsigned int exponent  : 11;
            unsigned int sign      : 1;
        };
    } ud;
    ud.d = (double)(bb & ~(bb >> 32)); // 消除高 32 位影響
    return ud.exponent - 1023;         // 偏移量 1023
}

此法依賴編譯器對 union 與位域的佈局，屬於未定義行為邊緣，速度視編譯器優化而定，失敗時返回 -1023。

總結與建議

性能優先、平台固定：優先用內建函數 __builtin_ctzll/__builtin_clzll（GCC/Clang）或 MSVC 的 _BitScanForward64/_BitScanReverse64，編譯器會自動選擇最優指令。
跨平台、無內建函數：採用德布魯因查表法（BSF）或分治查表法（BSR），無分支、常數時間、可移植。
教學/研究：匯編與浮點數法可加深對指令集與浮點表示的理解，生產環境慎用。

文中代碼源自開源社區（推測為 GNU 相關項目），版權歸原作者所有。