Function hamming::weight

pub fn weight(x: &[u8]) -> u64

Computes the Hamming weight of x, that is, the population count, or number of ones.

This is a highly optimised version of the following naive version:

fn naive(x: &[u8]) -> u64 {
    x.iter().fold(0, |a, b| a + b.count_ones() as u64)
}

This uses Lauradoux Cédric’s tree-merging approach (as implemented by Kim Walisch in primesieve) and achieves on the order of 1-2 cycles per byte.

Performance Comparison

length	naive (ns)	weight (ns)	naive/weight
1	5	16	0.31
10	29	51	0.56
100	284	392	0.72
1,000	2,780	340	8.2
10,000	27,700	2,300	12
100,000	276,000	17,900	15
1,000,000	2,770,000	172,000	16

Example

assert_eq!(hamming::weight(&[1, 0xFF, 1, 0xFF]), 1 + 8 + 1 + 8);