将位掩码值（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

您想要使用二进制对数：

#include <cmath>
double power = log2n(number);

Answer 2

如果枚举值是 2 的幂，那么我订阅已经建议 log2 的答案（他们比我先一步），但“建议”你使用一些“花哨的”Bit Twiddling Hacks（检查找到整数以 2 为底的对数部分）。

Answer 3

您本质上要求的是：“给定存储在整数 X 中的 2 的幂，找到指数 E 的最有效方法是什么？”

简单的方法是搜索那个重要的指数非零位：

int E = 0;
while (X >>= 1)
    E++;

请注意，这将为 X = 1 输出 E = 0 - 您可能需要将 E 初始化为 1 有 E = 1 表示 X = 1。

Answer 4

大多数现代CPU架构都有操作码来发现数字中最高或最低有效的非零位（例如，x86 上的 BSF 和 BSR）。这些也可作为某些编译器上的内在函数使用，例如 Microsoft 和 Intel 编译器上的 _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;

Answer 5

“求 x”的函数称为对数。在本例中为 log2。没有针对整数的标准 C log2 函数，计算是一个小循环。根据您的架构，您的 cpu 可能有一条 asm 指令来获取最高位，其作用相同。

在我看来，更好的解决方案是反过来。

定义类似的东西

#define PING 1
#define PANG 2
#define PONG 3
#define PUNG 4

（您也可以在此处使用枚举）。

然后在你的事件枚举中创建类似的东西

EventType_PING 1 << PING,
EventType_PANG 1 << PANG,
EventType_PONG 1 << PONG,
EventType_PUNG 1 << PUNG,