hamming_iter/
lib.rs

1#![no_std]
2
3/// Iterates over all `bits` width numbers in hamming weight order and
4/// sub-ordered by numerical order. Asserts that `bits < 64`.
5#[inline]
6pub fn hamming_iter(bits: u32) -> impl Iterator<Item = u64> {
7    assert!(bits <= 64);
8    if bits < 64 {
9        either::Left(
10            (0..=bits)
11                .flat_map(move |i| hamming_weight_iter(i).take_while(move |&n| n < 1 << bits)),
12        )
13    } else {
14        either::Right((0..=64).flat_map(hamming_weight_iter))
15    }
16}
17
18/// Iterate over all 64-bit integers with
19#[inline]
20pub fn hamming_weight_iter(weight: u32) -> impl Iterator<Item = u64> {
21    if weight < 2 {
22        either::Left(if weight == 0 {
23            either::Left(core::iter::once(0))
24        } else {
25            either::Right((0..64).map(|b| 1 << b))
26        })
27    } else {
28        // Find number of numbers with this distance.
29        let combinations = (64 - weight as usize + 1..=64)
30            .try_fold(1usize, |acc, n| acc.checked_mul(n))
31            .and_then(|n| {
32                (2..=weight as usize)
33                    .try_fold(1usize, |acc, n| acc.checked_mul(n))
34                    .map(|m| n / m)
35            });
36        either::Right(if let Some(combinations) = combinations {
37            either::Left(hamming_ascend((1 << weight) - 1).take(combinations))
38        } else {
39            either::Right(hamming_ascend((1 << weight) - 1))
40        })
41    }
42}
43
44/// Iterates over ascending equal hamming weight numbers starting at `start`.
45fn hamming_ascend(start: u64) -> impl Iterator<Item = u64> {
46    use core::num::Wrapping;
47    let mut acc = Wrapping(start);
48    core::iter::repeat(()).map(move |_| {
49        let res = acc.0;
50        let c = acc & ((!acc) + Wrapping(1));
51        let r = acc + c;
52        acc = (((r ^ acc) >> 2) / c) | r;
53        res
54    })
55}
hamming_iter/lib.rs

hamming_iter/
lib.rs
