CODEWITHSUNDEEP
rust
Fomalhaut
Fomalhaut

Reputation: 9755

How do I find the next power of 2 for a u64 integer in Rust efficiently?

I am searching for a fast way to find the next power of two for a 64-bit integer in Rust. For example, if I have 23 the result must be 32. I tried this code:

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
}

If gives correct results but the code does not look efficient and I believe there is a faster way to implement. Could anyone help? Asm code inside a Rust function is welcomed if it gains performance.

Upvotes: 4

Views: 3004

Answers (1)

kmdreko
kmdreko

Reputation: 60062

This function already exists in the standard library as u64::next_power_of_two:

Returns the smallest power of two greater than or equal to self.

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

If you're curious, its current implementation is roughly equal to:

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

Upvotes: 11

Related Questions