寻求将u8位扩展到u64各字节LSB的高效位操作优化方案

需求：将u8类型的每一位，映射到u64类型对应字节的最低有效位（LSB）。例如：
0b10110011 → 0x0100010100000101

你当前的实现无分支，但移位指令过多：

fn spread(x: u8) -> u64 {
    let x = x as u64;
    let y = (x * 0x0101010101010101) & 0x8040201008040201;
    (y | (y >> 1) | (y >> 2) | (y >> 3) | (y >> 4) | (y >> 5) | (y >> 6) | (y >> 7))
        & 0x0101010101010101
}

对应的汇编包含大量移位指令，以下是两种优化思路：

1. 分治法减少移位次数 #

利用位运算的分治思想，将多次移位合并为3次，大幅减少指令数量：

fn spread(x: u8) -> u64 {
    let x = x as u64;
    let mut y = (x * 0x0101010101010101) & 0x8040201008040201;
    // 分步骤填充字节内的低位
    y |= y >> 1;  // 每个字节内的连续2位变为1
    y |= y >> 2;  // 扩展为连续4位
    y |= y >> 4;  // 扩展为整个字节的8位
    // 保留每个字节的LSB
    y & 0x0101010101010101
}

优化原理 #

原代码需要7次移位或运算来填充字节内的所有低位，分治法通过「2位→4位→8位」的逐步扩展，仅需3次移位或操作即可达到相同效果，生成的汇编指令数量会显著减少。

2. 查找表法（最优性能） #

由于u8仅有256种可能的取值，可预计算所有结果并存储在数组中，查询时直接返回对应值，完全避免运算开销：

const SPREAD_TABLE: [u64; 256] = {
    let mut table = [0; 256];
    let mut i = 0;
    while i < 256 {
        let mut val = 0;
        let x = i as u8;
        for j in 0..8 {
            if x & (1 << j) != 0 {
                // 将x的第j位映射到u64的第j个字节的LSB
                val |= 1 << (j * 8);
            }
        }
        table[i] = val;
        i += 1;
    }
    table
};

fn spread(x: u8) -> u64 {
    SPREAD_TABLE[x as usize]
}

优势 #

该方法的汇编仅包含movzx和数组索引指令，是性能最优的方案——无任何位运算、乘法或移位，仅需一次内存读取（数组在编译时会被优化为只读数据段，访问速度极快）。

内容的提问来源于stack exchange，提问作者twig-froth