Function hamming::distance

pub fn distance(x: &[u8], y: &[u8]) -> u64

Computes the bitwise Hamming distance between x and y, that is, the number of bits where x and y differ, or, the number of set bits in the xor of x and y.

When x and y have the same 8-byte alignment, this uses distance_fast, a highly optimised version of the following naive version:

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

If alignments differ, a slower but less restrictive algorithm is used.

It is essentially guaranteed that x and y will have the same 8-byte alignment if they are both just Vec<u8>s of non-trivial length (e.g. larger than 8) as in the example below.

Panics

x and y must have the same length, or else distance panics.

Performance Comparison

length	naive (ns)	distance (ns)	naive/distance
1	5	6	0.83
10	44	45	0.97
100	461	473	0.97
1,000	4,510	397	11
10,000	46,700	2,740	17
100,000	45,600	20,400	22
1,000,000	4,590,000	196,000	23

The benchmarks ensured that x and y had the same alignment.

Examples

let x = vec![0xFF; 1000];
let y = vec![0; 1000];
assert_eq!(hamming::distance(&x, &y), 8 * 1000);