GCC中是否有Intel intrinsic实现该位选择操作？及高效方案问询

我有一个16位无符号整数U，以及十个16位无符号整数T1、T2……T10。每个TX对应一个16位掩码MX，TX的值是提取U中MX为1的位并连续排列的结果，示例如下：

U:     0010101101001110
MX:    0010111010101011

忽略MX中0对应的U的位后，将选中的位连续排列得到TX：

U:     --1-101-0-0-1-10
MX:    0010111010101011
TX:    1101001100000000

选中的8位可排列在TX的任意连续区域，只要位置确定即可。现问询：

1. 该操作的最高效实现方式是什么？
2. 如何实现每个MX对应操作的常数时间执行？
3. GCC是否提供可用的Intel intrinsic？
4. 是否有MMX指令可批量处理2或4个TX？

问题解答 #

1. 最高效实现方式 #

分两种场景处理：

• 固定掩码：预计算查找表（LUT）是最优方案。16位无符号整数总共只有65536种可能值，针对每个MX提前生成一个65536项的数组，数组索引对应U的取值，存储值就是处理后的TX。运行时直接查表，单次操作仅需一次内存访问，速度最快。
• 动态掩码：依赖Intel BMI2指令集的pext（位提取）指令，一条硬件指令就能完成位提取与重排，比手动移位、掩码组合的软件实现效率高得多。

2. 常数时间执行的实现 #

• 固定掩码：直接使用预计算的LUT，不管U取什么值，查表返回结果，完全是常数时间操作。
• 动态掩码：如果CPU支持BMI2指令集，调用pext指令即可，这是硬件级别的固定周期执行，属于常数时间。若没有BMI2支持，可以预计算掩码MX的位位置映射表，提前记录MX中所有1位在U中的位置，再通过移位拼接的方式一次性组合出TX，这种软件实现步骤固定，也是常数时间，只是比硬件指令慢。

3. GCC对Intel intrinsic的支持 #

GCC完全支持BMI2指令集的intrinsic函数，针对16位无符号整数：

• 位提取用__builtin_ia32_pext_u16，对应硬件指令pextw；
• 若需要反向操作（将连续位散布到指定位置），用__builtin_ia32_pdep_u16，对应pdepw指令。
  编译时需添加-mbmi2选项开启BMI2支持，且目标CPU需支持该指令集（比如Intel Haswell及之后、AMD Ryzen及之后的型号）。

4. MMX指令的批量处理可行性 #

MMX指令集没有专门的位提取重排指令，无法直接批量处理2或4个16位的TX操作。如果想用MMX尝试打包处理，只能把多个16位的U和掩码塞进64位MMX寄存器，再循环逐个处理，本质还是串行操作，没有真正的批量加速效果。若需要批量处理，更推荐用SSE/AVX配合BMI2，或者AVX-512的位操作指令，能实现更高效的批量位处理。

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