C语言中高效提取掩码有效位对应整数的实现方法问询

核心需求 #

给定位掩码b（示例：0b1010110，其中包含4个置1位）和整数m，需要将m & b的结果转换为0~2^k-1之间的整数（k为b中置1位的数量）——也就是把m & b中对应b置1位的有效位，紧凑排列成连续的低k位，且不能硬编码b的位信息，同时追求比O(B)（B为b中置1位数量）更快的效率。

高效实现方案 #

1. 硬件指令直接实现（O(1)） #

如果目标平台支持x86架构的PEXT（并行位提取）指令，这是最优解。该指令可以直接从源数中提取掩码指定的位，并将它们紧凑排列到结果的低位。

在C/C++中，可通过编译器内置函数调用：

#include <immintrin.h>
// 32位版本
uint32_t result = _pext_u32(m, b);
// 64位版本
uint64_t result = _pext_u64(m, b);

这个操作是硬件级别的单周期指令，完全满足O(1)复杂度，且不需要依赖b的位数组信息。

2. 预计算乘法掩码（O(1)单次操作，O(B)预计算） #

如果无法使用硬件指令，可以预计算一个压缩乘法掩码，之后每次转换只需要一次乘法和移位操作。

预计算逻辑：

假设b中有k个置1位，对应的位索引存在数组bits[]中（比如示例中bits = {1,2,4,6}），我们需要为每个源位s（即bits[i]）分配一个目标位i（0~k-1）。构造乘法掩码compress_mask，使得(m & b) * compress_mask后，所有目标位会被对齐到结果的低k位。

掩码计算代码示例：

uint64_t compress_mask = 0;
int k = sizeof(bits)/sizeof(bits[0]);
for (int i = 0; i < k; i++) {
    // 每个源位s对应目标位i，乘法时会将源位的1移动到s+i位
    compress_mask |= 1ULL << (bits[i] + i);
}

转换操作：

uint32_t x = m & b;
uint32_t result = (uint32_t)((uint64_t)x * compress_mask >> (64 - k));

预计算只需执行一次，之后每次转换都是O(1)的乘法和移位，适合b固定的场景。

3. SWAR分组压缩（O(log W)，W为整数位数） #

如果b是动态变化的，且不想做预计算，可以用SWAR（单寄存器内模拟SIMD）技术，通过分组移位逐步将分散的位聚集到低位，复杂度为O(log W)（W为整数的位数，比如32位只需5步）。

核心思路是通过多次移位与掩码操作，将分散的位逐步合并：

uint32_t x = m & b;
// 第一步：处理每2位，将偶数位的有效位移到奇数位的空位
x = (x & 0x55555555) | ((x & 0xAAAAAAAA) >> 1);
// 第二步：处理每4位，将高2位的有效位移到低2位的空位
x = (x & 0x33333333) | ((x & 0xCCCCCCCC) >> 2);
// 第三步：处理每8位
x = (x & 0x0F0F0F0F) | ((x & 0xF0F0F0F0) >> 4);
// 第四步：处理每16位
x = (x & 0x00FF00FF) | ((x & 0xFF00FF00) >> 8);
// 第五步：合并32位
x = (x & 0x0000FFFF) | ((x & 0xFFFF0000) >> 16);
// 最后提取低k位
uint32_t result = x & ((1 << k) - 1);

这个方法会压缩所有置1位到低位，正好符合需求，且不需要依赖b的位数组，操作次数固定为log₂(W)次。

内容的提问来源于stack exchange，提问作者return true