Multiply by De Bruijn sequence and lookup index

Programming

Computing the base‑2 logarithm of an integer (more precisely: finding the index of the highest set bit) is a common operation in systems programming, graphics, data compression, and low‑level algorithms. While Rust provides methods like u32::leading_zeros(), sometimes you may want your own implementation—especially an approach that is branch‑free, fast, and works on all stable targets.

One elegant solution is the De Bruijn bit twiddling method, a classic technique from the world of high‑performance low‑level programming.

fn main() {
    let x = 1024u32;
    println!("log2(1024) = {}", log2_debruijn(x)); // Ausgabe: 10
    println!("log2(256) = {}", log2_debruijn(256)); // Ausgabe: 8
}

const MULTIPLY_DEBRUIJN_BIT_POSITION: [u32; 32] = [
     0,  9,  1, 10, 13, 21,  2, 29,
    11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 15, 17, 19, 24,  7,
    23,  6, 26,  5, 28,  4, 31, 27,
];

fn log2_debruijn(mut v: u32) -> u32 {
    // propagate highest set bit
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;

    // multiply by De Bruijn sequence and lookup index
    let index = ((v.wrapping_mul(0x07C4ACDD)) >> 27) as usize;

    MULTIPLY_DEBRUIJN_BIT_POSITION[index]
}