将2位掩码的幂转换为相应的索引

Question

我一直在寻找这个问题的答案，但没有找到任何合适的解决方案。我正在尝试将单个启用位（32 位掩码）转换为其相应的索引位置。该掩码仅启用了一位，从位 0 到位 31。

因此，这是我正在寻找的转换： 1=1、2=2、4=3、8=4、16=5、32=6 等等。

我不反对创建一个查找表，如果该表不是很大而且大部分是空的。是否有任何聪明的数学可以一步完成这一任务（无需循环遍历这些位）？

编辑：我在提供的链接中找不到满意的答案。但在闲逛了一些数字之后，我确实偶然发现了一个神奇的值，它可以完美地分离 32 位掩码的两个值的幂。该值为 37。如果您将任何 32 位 2 的幂值调制为 37，它将将该 2 的幂值转换为 1 - 36 之间的索引。这意味着我们可以创建一个包含 37 个值的小型查找表，仅浪费了一些条目。这是该表的填充率： |0|1|1|1|1|1|1|0|1|1|1|1|1|1|0|1|1|1|1|0|1|1|1|1|1 |1|1|1|0|1|1|1|1|1|1|1|1|

我将进一步尝试一下，看看 64 位值是否可以实现这样的事情。

我不明白为什么这个论坛这么快就结束话题了。这使得不可能对以前讨论过的事情进行任何类型的讨论。

Answer 1

这是一个受 Bit Twiddling Hacks 启发的解决方案：

• 首先将值递减为将索引下面的所有位设置为 1
• ，然后计算结果值中的位数，
• 添加 1 以获得预期结果

int bit_index(uint32_t v) {
    v -= 1;
    v = v - ((v >> 1) & 0x55555555);                // reuse input as temporary
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
    return 1 + (((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); // count
}

Answer 2

只需将位向右移动，直到全部为零：

#include <stdio.h>

int main(void)
{
    int n, pos, x;

    n = scanf("%d", &x);
    if (n == 1) {
        pos = 0;
        while (x != 0) {
            x >>= 1;
            pos++;
        }
        printf("%d\n", pos);
    }
    return 0;
}