获取 64 位整数内的位位置数组 [英] Get an array of the bit positions within a 64-bit integer

问题描述

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

OK, it may sound a bit complicated, but this is what I'm trying to do :

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

• Take e.g. 10101010101
• And return { 0, 2, 4, 6, 8, 10 } - an array with all of the positions of bits which are set

这是我的代码:

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
• 两种方法都是静态内联.

• UINT is a typedef of unsigned int
• U64 is a typedef of unsigned long long
• Both methods are static inline.

推荐答案

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

Here is another suggestion that can be profiled (can be combined with other suggestions for further optimization). Note, the loop here is 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;
}

这篇关于获取 64 位整数内的位位置数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！