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.

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

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.

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:

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