How do I convert a C function that counts the number of ones in a 9-bit bitmask to Rust?

Question

I have a u16 which I use to hold a 9-bit bitmask and I want to find out how many 1s it contains.

I found this algorithm that I have no clue how or why it works:

/* count number of 1's in 9-bit argument (Schroeppel) */
unsigned count_ones(unsigned36 a) {
  return ((a * 01001001001)     /* 4 adjacent copies */
             & 042104210421)    /* every 4th bit */
             % 15;              /* casting out 15.'s in hexadecimal */
}

How can I turn this into a Rust function? This is what I've tried but doesn't work:

fn main() {
    let a: u16 = 0b101_100_000;
    println!("Ones in {:b}: {}", a, num_of_ones(a));
}

fn num_of_ones(quantity: u16) -> u8 {
    (((quantity as u64 * 01_001_001_001) & 042_104_210_421) % 15) as u8
}

score 4 · Accepted Answer · answered Sep 22 '20 at 20:41

A leading zero in C denotes an octal literal. Rust octals start with 0o, like the 0b you already use:

(((quantity as u64 * 0o01_001_001_001) & 0o042_104_210_421) % 15) as u8

However, there's no need for this as it's built-in, such as u16::count_ones:

println!("Ones in {:b}: {}", a, a.count_ones());

How do I convert a C function that counts the number of ones in a 9-bit bitmask to Rust?

1 Answers1