如何有效地为锈蚀中的u64整数求下2的幂？

Question

我正在寻找一种快速的方法，以找到下一个二次方的64位整数在锈蚀。例如，如果我有23，则结果必须是32。我试过这个代码：

fn ceil_pow2(x: u64) -> u64 {
    let mut y: u64 = x;
    let mut z: u64 = 1;
    while y > 0 {
        y >>= 1;
        z <<= 1;
    }
    if z == 2 * x {
        z >>= 1;
    }
    z
}

如果给出了正确的结果，但是代码看起来并不有效，我相信有一个更快的实现方法。有人能帮忙吗?锈蚀函数中的Asm代码如果能获得性能，就会受到欢迎。

Answer 1

此函数已以u64::next_power_of_two形式存在于标准库中。

返回大于或等于self的最小幂。

fn ceil_pow2(x: u64) -> u64 {
    x.next_power_of_two()
}

如果您好奇的话，它当前的实现大致相当于：

fn next_power_of_two(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        (u64::MAX >> (n - 1).leading_zeros()) + 1
    }
}