c++ - 将位掩码值(1、2、4、8 等)映射到 vector 索引(1、2、3、4 等)的有效方法

Question

我有一个包含一组值的枚举，这些值可以按位或在一起:

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

我希望此枚举最多包含 15-20 个项目。在收到这些枚举值之一时，我希望能够将其映射到一个 vector ，但我不想使用稀疏数组，而是希望将这些值折叠起来。将 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 架构都有操作码来发现数字中最高或最低有效的非零位(例如，x86 上的 BSF and BSR)。这些在某些编译器上也可用作内部函数，例如 Microsoft 和 Intel 编译器上的 _BitScanForward 和 _BitScanReverse。

上面的位扫描无疑是最快的解决方案。对于更便携的解决方案，向右移动直到钻头从末端掉落:

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

请注意，这将返回 0、1、2、3，这比 1、2、3、4 更适合 vector 索引。

一个更复杂但更快的可移植解决方案是二进制印章:

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