如何在Rust中有效地找到u64整数的下一个2幂？

html5 • • 问答

我正在寻找一种快速的方法来在 Rust 中找到 64 位整数的下一个 2 的幂。例如，如果我有 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如果 Rust 函数内的代码能提高性能，它是受欢迎的。

回答

此函数已存在于标准库中，如下所示u64::next_power_of_two：

返回大于或等于 的 2 的最小幂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
    }
}

  • @thebusybee No loops required! This technically depends on the target ISA (x86, ARM, etc.), but this operation is common enough that most have a `clz` (count-leading-zeros) or `ffs` (find-first-set) instruction that does this in hardware: [wikipedia](https://en.wikipedia.org/wiki/Find_first_set)
以上是如何在Rust中有效地找到u64整数的下一个2幂？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>