haar_lib/algo/enum_bit/
superset_desc.rs

1//! ビット列の上位集合を降順に列挙する
2use std::iter::successors;
3
4/// ビット列としての`a`の上位集合を降順に列挙するイテレータを返す。
5pub fn superset_desc(a: u32, n: u32) -> impl Iterator<Item = u32> {
6    let x = (1 << n) - 1;
7    let y = x ^ (a & x);
8
9    successors(Some(y), move |&t| t.checked_sub(1).map(|x| x & y)).map(move |t| t | a)
10}
11
12#[cfg(test)]
13mod tests {
14    use super::*;
15    use test_case::test_case;
16
17    #[test_case(0b11111111, 8)]
18    #[test_case(0b00000000, 8)]
19    #[test_case(0b10101010, 8)]
20    #[test_case(0b00000001, 8)]
21    #[test_case(0b10000000, 8)]
22    #[test_case(0b10000001, 8)]
23    #[test_case(0b11011011, 8)]
24    fn check(x: u32, n: u32) {
25        let a = (0..1 << n)
26            .rev()
27            .filter(|i| (x & !i) == 0)
28            .collect::<Vec<_>>();
29
30        let b = superset_desc(x, n).collect::<Vec<_>>();
31
32        assert_eq!(a, b);
33    }
34}