toolbox_rs/
math.rs

1use num::{Integer, PrimInt};
2
3pub fn choose(n: u64, k: u64) -> u64 {
4    if k > n {
5        return 0;
6    }
7
8    if k == 0 || k == n {
9        return 1;
10    }
11
12    let k = if k > n - k { n - k } else { k };
13
14    let mut result = 1;
15    for i in 1..=k {
16        result = result * (n - i + 1) / i;
17    }
18
19    result
20}
21
22/// calculate the largest power of 2 less or equal to n
23pub fn prev_power_of_two<T: PrimInt>(n: T) -> T {
24    if n == T::zero() {
25        return T::zero();
26    }
27    let leading_zeros = n.leading_zeros() as usize;
28    let sizeof = 8 * std::mem::size_of::<T>();
29    T::one() << (sizeof - leading_zeros - 1)
30}
31
32/// computes the least-significant bit set.
33pub fn lsb_index<T: Integer + PrimInt>(n: T) -> Option<u32> {
34    if n == T::zero() {
35        return None;
36    }
37
38    Some(n.trailing_zeros())
39}
40
41/// computes the least-significant bit set. Doesn't return the correct answer if the input is zero
42pub fn non_zero_lsb_index<T: Integer + PrimInt>(n: T) -> u32 {
43    if n == T::zero() {
44        return 0;
45    }
46
47    n.trailing_zeros()
48}
49
50#[cfg(test)]
51mod tests {
52    use crate::math::{choose, lsb_index, non_zero_lsb_index, prev_power_of_two};
53
54    #[test]
55    fn some_well_known_n_choose_k_values() {
56        let test_cases = [
57            ((64u64, 1u64), 64u64),
58            ((64, 63), 64),
59            ((9, 4), 126),
60            ((10, 5), 252),
61            ((50, 2), 1_225),
62            ((5, 2), 10),
63            ((10, 4), 210),
64            ((37, 17), 15905368710),
65            ((52, 5), 2598960),
66        ];
67
68        test_cases.into_iter().for_each(|((n, k), expected)| {
69            assert_eq!(choose(n, k), expected);
70        });
71    }
72
73    #[test]
74    fn lsb_well_known_values() {
75        assert_eq!(lsb_index(0), None);
76        assert_eq!(lsb_index(10), Some(1));
77        assert_eq!(lsb_index(16), Some(4));
78        assert_eq!(lsb_index(255), Some(0));
79        assert_eq!(lsb_index(1024), Some(10));
80        assert_eq!(lsb_index(72057594037927936_i64), Some(56));
81    }
82
83    #[test]
84    fn lsb_index_well_known_values() {
85        assert_eq!(non_zero_lsb_index(0), 0);
86        assert_eq!(non_zero_lsb_index(10), 1);
87        assert_eq!(non_zero_lsb_index(16), 4);
88        assert_eq!(non_zero_lsb_index(255), 0);
89        assert_eq!(non_zero_lsb_index(1024), 10);
90        assert_eq!(non_zero_lsb_index(72057594037927936_i64), 56);
91    }
92
93    #[test]
94    fn largest_power_of_two_less_or_equal() {
95        assert_eq!(prev_power_of_two(16_u8), 16);
96        assert_eq!(prev_power_of_two(17_i32), 16);
97        assert_eq!(prev_power_of_two(0x5555555555555_u64), 0x4000000000000)
98    }
99}
toolbox_rs/math.rs

toolbox_rs/
math.rs
