使用位操作将位从8字节数字中的每个字节转换为单个字节

Question

我有一个64位无符号整数。我想检查每个字节的第6位，并返回代表这些第6位的单个字节。

显而易见的“强力”解决方案是：

inline const unsigned char Get6thBits(unsigned long long num) {
    unsigned char byte(0);
    for (int i = 7; i >= 0; --i) {
        byte <<= 1;
        byte |= bool((0x20 << 8 * i) & num);
    }

    return byte;
}

我可以将循环展开为一串串联的|语句，以避免int分配，但这仍然很丑陋。

有更快，更聪明的方法吗？也许使用位掩码来获取第6位，0x2020202020202020然后以某种方式将其转换为字节？

Answer 1

如果_pext_u64有可能（这种方法在Haswell及更高版本上可以使用，但在Ryzen上则很慢），您可以这样编写：

int extracted = _pext_u64(num, 0x2020202020202020);

这是一种真正的实现方式。pext接受一个值（第一个参数）和一个掩码（第二个参数），在掩码具有设置位的每个位置上，它从值中获取相应的位，并将所有位连接在一起。

_mm_movemask_epi8 更广泛地使用，您可以像这样使用它：

__m128i n = _mm_set_epi64x(0, num);
int extracted = _mm_movemask_epi8(_mm_slli_epi64(n, 2));

pmovmskb接受其输入向量中每个字节的高位并将其连接。我们想要的位不是每个字节的高位，因此我将它们向上移动两个位置psllq（当然您可以num直接移位）。这_mm_set_epi64x只是num进入向量的某种方式。

不要忘了#include <intrin.h>，并且这些都没有经过测试。

Codegen 似乎足够合理

一个怪异的选项正在乘以乘法收集位：（仅经过稍微测试）

int extracted = (num & 0x2020202020202020) * 0x08102040810204 >> 56;

这里的想法是num & 0x2020202020202020只设置了很少的位，因此我们可以安排一种产品，它永远不会携带到我们需要的位（或根本不需要位）。乘法器被构造为执行以下操作：

a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000 +
0b0000000c0000000d0000000e0000000f0000000g0000000h00000000000000 +
00c0000000d0000000e0000000f0000000g0000000h000000000000000000000 etc..

然后，最高字节将所有位“压缩”在一起。较低的字节实际上也有类似的东西，但是它们缺少了必须来自“较高”的位（位只能在乘法运算中向左移动）。