c++ - 获取 64 位整数内的位位置数组

Question

好的，听起来可能有点复杂，但这就是我想要做的:

• 举个例子10101010101
• 并返回 { 0, 2, 4, 6, 8, 10 } - 一个包含所有已设置位位置的数组

这是我的代码:

UINT DQBitboard::firstBit(U64 bitboard)
{
    static const int index64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5  };

    static const U64 debruijn64 = 0x07EDD5E59A4E28C2ULL;

    #pragma warning (disable: 4146)
    return index64[((bitboard & -bitboard) * debruijn64) >> 58];  
}

vector<UINT> DQBitboard::bits(U64 bitboard)
{
    vector<UINT> res;

    while (bitboard)
    {
        UINT first = DQBitboard::firstBit(bitboard);
        res.push_back(first);

        bitboard &= ~(1ULL<<first);
    }

    return res;
}

而且代码肯定确实有效。

我的观点是:

• 您有什么更快的实现方案吗？
• 您发现有什么可以优化的地方吗？如果有，是什么？

---

提示:

• UINT 是 unsigned int
的 typedef
• U64 是 unsigned long long
的 typedef
• 这两种方法都是静态内联。

Answer 1

这是另一个可以分析的建议(可以与其他建议结合以进行进一步优化)。注意，这里的循环是O(number of set bits)。

vector<UINT> bits_set (UINT64 data) 
{
    UINT n;
    vector<UINT> res;
    res.reserve(64);
    for (n = 0; data != 0; n++, data &= (data - 1))
    {
        res.push_back(log2(data & ~(data-1)));
    }
    return res;
}