将位掩码值(1,2,4,8等)映射到向量索引(1,2,3,4等)的有效方法

Question

我有一组可以按位或一起使用的值:

enum EventType_e
{
    EventType_PING  = 1,
    EventType_PANG  = 2,
    EventType_PONG  = 4,
    EventType_PUNG  = 8
};

我希望这个枚举增长到最多包含15-20个项目.在接收到这些枚举值中的一个时,我希望能够将其映射到向量,但是我不想使用稀疏数组来折叠值.将1,2,4,8,16,32映射到1,2,3,4,5,6的最佳方法是什么(即在2 ^ x = 1,2 ^ x = 2,2中找到'x' ^ x = 4,2 ^ x = 8等)

Answer 1

大多数现代CPU架构有操作码来发现最多或最少显著不为零的数字(例如,位BSF和BSR在x86).这也可作为一些编译器,如内部函数_BitScanForward和_BitScanReverse对微软和英特尔的编译器.

上述位扫描是最快的解决方案.对于更便携的解决方案,向右移动直到钻头从末端下降:

int i;
for (i = 0; n >>= 1; ++i) { }

请注意,这将返回0,1,2,3,这更适合于矢量索引而不是1,2,3,4.

更复杂但更快速的便携式解决方案是二进制印章:

// Logically, we initialise i to 0, and add n - 1 at the end. Initialising
// to -1 avoids the subtraction. This is splitting hairs somewhat, and who
// knows — initialising to -1 instead of zero might be slow!
int i = -1;
if (n >> 16) { n >>= 16; i += 16; }
if (n >>  8) { n >>=  8; i +=  8; }
if (n >>  4) { n >>=  4; i +=  4; }
if (n >>  2) { n >>=  2; i +=  2; }
i += n;