Bit twiddling: n: i32, 2^(i+1) > n >= 2^i => compute i

We have a n: i32.
We know that 2^(i+1) > n >= 2^i.
What is the fastest way to calculate i ?

Slow way:floor(ln_2(n)).

Wondering if there is some bit twiddling trick.

i32::BITS - 1 - n.leading_zeros()

Or:
n.log2() (nightly experimental API)

2 Likes

Any insights on how this is implemented? The [src] link is beyond my comprehension

ctlz in std::intrinsics - Rust


Compiler Explorer


BSR — Bit Scan Reverse

4 Likes

So the key idea is BSR — Bit Scan Reverse and subtract it from 31? Was not aware such x86_64 instr existed. Need to get into the habit of using compiler explorer. :slight_smile:

On most CPUs there is a built-in instructions that does this in a single step. That's what it will compile to (modulo taking care of special cases).

Without using the built-in instructions, it can be done in O(log 32) steps using binary search:

pub fn log2(mut x: u32) -> u32 {
    let mut res = 0;
    for i in (0..5).rev() {
        let bits = 1 << i;
        if x >= 1 << bits {
            x >>= bits;
            res += bits;
        }
    }
    res
}

Insterestingly, there is a theoretical O(1) algorithm for this using regular arithmetic instructions for any word size. It's extremely complicated, for a O(1) algorithm! Not very practical for realistic word sizes like 32, but it's interesting that it's possible:
https://www.akalin.com/constant-time-mssb

3 Likes

Ah, here we go… passing -Ctarget-cpu=native on godbolt does the trick:

Compiler Explorer

and the context menu on the assembly instruction there links to LZCNT — Count the Number of Leading Zero Bits

You might be interested in reading through the intrinsics that LLVM offers: https://llvm.org/docs/LangRef.html#bit-manipulation-intrinsics.

You can also read through the approaches for machines that don't have such an intrinsic: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.