如何从64位整数的每个字节提取最高有效位生成8位掩码？

核心思路 #

我们需要从64位整数的每个字节中提取最高有效位（第7位，从0开始计数），将这些位拼接成一个8位掩码。可以通过位运算结合乘法技巧高效实现，避免循环操作。

实现方案 #

方法一：乘法+移位的高效组合 #

你之前尝试的乘法思路方向正确，但需要调整常数。正确的魔法常数是0x8040201008040201ULL，它的每个字节最高位为1，且位置对应提取位的权重。具体步骤：

1. 用0x8080808080808080ULL与输入值按位与，仅保留每个字节的最高位。
2. 将结果乘以魔法常数，该操作会把每个字节的最高位映射到结果的高8位对应位置。
3. 将最终结果右移56位，得到8位掩码。

代码实现：

auto extract_msbs(uint64_t mask) -> uint8_t {
    const uint64_t msb_mask = 0x8080808080808080ULL;
    const uint64_t magic = 0x8040201008040201ULL;
    return static_cast<uint8_t>((mask & msb_mask) * magic >> 56);
}

验证测试 #

• 对示例输入0x0011001000010111000000101100111000100000110011010101100001111011，执行后得到00010100，与预期一致。
• 对测试用例0x0000000000000080，执行后得到00000001，符合正确结果。

方法二：纯位运算实现（兼容多架构） #

若担心乘法指令的性能或兼容性，可采用纯位运算方案：

auto extract_msbs(uint64_t mask) -> uint8_t {
    uint64_t t = mask & 0x8080808080808080ULL;
    t = (t >> 7) | (t >> 14) | (t >> 21) | (t >> 28) |
        (t >> 35) | (t >> 42) | (t >> 49) | (t >> 56);
    return static_cast<uint8_t>(t & 0xFF);
}

该方法通过将每个字节的最高位移至最低位，再通过或运算聚合所有位，最终取低8位得到结果。

性能说明 #

第一种方法利用CPU乘法指令，在现代x86架构上仅需3条指令（AND、MUL、SHR），性能最优。第二种方法完全使用位运算，适合乘法性能较弱的架构。

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