Why does my Hamming weight function work in C but not in Rust?

Question

I've got the following Hamming weight code in Rust, and it returns garbage for 0xffff and 0xffffffff, but the identical code in C works, so I must be misunderstanding something about how Rust does bit-level operations. It's completely parenthesized, so I don't think it's an operator-precedence issue.

In C:

#include <stdio.h>

int hamming_weight(int val) {
    int v1 = val - ((val >> 1) & 0x55555555);
    int v2 = (v1 & 0x33333333) + ((v1 >> 2) & 0x33333333);
    return (((v2 + (v2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

int main() {
    printf("%x -> %d\n", 7, hamming_weight(7));
    printf("%x -> %d\n", 0xff, hamming_weight(0xff));
    printf("%x -> %d\n", 0xffff, hamming_weight(0xffff));
    printf("%x -> %d\n", 0xffffffff, hamming_weight(0xffffffff));
    return 0;
}

The results:

7 -> 3
ff -> 8
ffff -> 16
ffffffff -> 32

In Rust (I had to use u64 to prevent overflow panics on 0xffff):

fn hamming_weight(val: u64) -> u64 {
    let v1 = val - ((val >> 1) & 0x55555555);
    let v2 = (v1 & 0x33333333) + ((v1 >> 2) & 0x33333333);
    (((v2 + (v2 >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24
}

fn main() {
    println!("{:x} {}", 7, hamming_weight(7));
    println!("{:x} {}", 0xff, hamming_weight(0xff));
    println!("{:x} {}", 0xffff, hamming_weight(0xffff));
    println!("{:x} {}", 0xffffffffu32, hamming_weight(0xffffffffu64));
}

The results:

7 3
ff 8
ffff 2064
ffffffff 135272480

I'm using Rust 1.16. I know Rust has count_ones() - the compiler told me when I was writing this code, which was pretty amazing, but I am choosing to not use it.

Answer 1

I had to use u64 to prevent overflow panics on 0xffff

That's your problem. The original C code relies on the operation overflowing. Increasing the size of the type doesn't fix it, but allowing the overflow to wrap does:

fn hamming_weight(val: u32) -> u32 {
    let v1 = val - ((val >> 1) & 0x55555555);
    let v2 = (v1 & 0x33333333) + ((v1 >> 2) & 0x33333333);
    (((v2 + (v2 >> 4)) & 0xF0F0F0F).wrapping_mul(0x1010101)) >> 24
}