好的,听起来可能有点复杂,但这就是我想要做的:
- 举个例子
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
- 这两种方法都是
静态内联
。
最佳答案
这是另一个可以分析的建议(可以与其他建议结合以进行进一步优化)。注意,这里的循环是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;
}
关于c++ - 获取 64 位整数内的位位置数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14086854/