rust - 如何有效地将数字n转换为设置了那么多位数的整数？例如8-> 0b11111111？

Question

您如何有效地将数字n转换为设置了这么低的低有效位的数字？也就是说，对于8位整数:

0 -> 00000000
1 -> 00000001
2 -> 00000011
3 -> 00000111
4 -> 00001111
5 -> 00011111
6 -> 00111111
7 -> 01111111
8 -> 11111111

似乎微不足道:

fn conv(n: u8) -> u8 { (1 << n) - 1 }

但这不是:

thread 'main' panicked at 'attempt to shift left with overflow', src/main.rs:2:5

playground
这是因为在Rust中，不能将N位的数字左移N位。在许多体系结构上，这是未定义的行为。u8::MAX >> (8 - n)也不起作用，因为右移具有相同的溢出限制。
那么，在没有查找表或条件表的情况下实现此目标的有效方法是什么？或者这是不可能的，因此必须采取一种类似的实现:

fn conv2(n: u8) -> u8 {
    match 1u8.checked_shl(n.into()) {
        Some(n) => n - 1,
        None => u8::MAX,
    }
}

Answer 1

对于任何小于最大 native 整数大小的位宽度，最有效的方法几乎肯定是使用较宽的类型进行计算，然后将其范围缩小为输出类型:

pub fn conv(n: u8) -> u8 {
    ((1u32 << n) - 1) as u8
}

rustc 1.50 at -C opt-level=1 or higher将其呈现为四个没有分支或间接指示的指令，这可能是x86-64的最佳选择。

example::conv:
        mov     ecx, edi
        mov     eax, 1
        shl     eax, cl
        add     al, -1
        ret

在大多数(全部？)32位或更大的平台上，使用u8或u16而不是u32进行数学运算不会获得任何好处；如果必须使用32位寄存器，则最好也使用整个寄存器(这也是certain integer methods only accept u32 的原因)。
即使您编写match，也可能不会将其编译为分支。在我的测试中，以下功能

pub fn conv(n: u32) -> u64 {
    match 1u64.checked_shl(n) {
        Some(n) => n - 1,
        _ => !0,
    }
}

编译时不带分支，只有cmov指令，并使用(软件仿真的)u128将pretty similar看起来等效。在假设match是一个问题之前，请务必先进行概要分析。