得到内的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

这是我的code：

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

而code肯定的不工作

我的观点是：

• 有没有更快的实现，你有什么想法？
• 请您注意任何可能进行优化？如果有，是什么？

提示：

• UINT 是 unsigned int类型的一个typedef
• U64 是一个typedef 无符号长长
• 在这两种方法都静态内联。

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

推荐答案

下面是另一个建议，可异形（可以与其他建议进行进一步的优化组合）。请注意，这里的循环是 O（组位数）。

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屋！