获取 64 位整数内的位位置数组

本文介绍了获取 64 位整数内的位位置数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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