arbi 0.7.0

Arbitrary Precision Integer
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

/*
Copyright 2025 Owain Davies
SPDX-License-Identifier: Apache-2.0 OR MIT
*/

use crate::{Arbi, BitCount, Digit};

impl Arbi {
    /// If this integer is nonzero, returns the number of trailing zeros in the
    /// binary representation (two's complement) of `self`. Otherwise, returns
    /// `None`.
    ///
    /// # Examples
    /// ```
    /// use arbi::Arbi;
    /// assert_eq!(Arbi::zero().trailing_zeros(), None);
    /// assert_eq!(Arbi::from(0xFFFFFFFF00000000u64).trailing_zeros(), Some(32));
    /// ```
    ///
    /// # Complexity
    /// \\( O(n) \\)
    pub fn trailing_zeros(&self) -> Option<BitCount> {
        let first_nonzero = self.vec.iter().position(|&digit| digit != 0)?;
        Some(
            self.vec[first_nonzero].trailing_zeros() as BitCount
                + first_nonzero as BitCount * Digit::BITS as BitCount,
        )
    }
}

#[cfg(test)]
mod tests {
    use crate::util::test::{get_seedable_rng, get_uniform_die, Distribution};
    use crate::Arbi;
    use crate::{BitCount, DDigit, Digit};
    use alloc::vec;

    macro_rules! assert_trailing_zeros {
        ($value:expr) => {
            let arbi = Arbi::from($value);
            assert_eq!(
                arbi.trailing_zeros(),
                if $value == 0 {
                    None
                } else {
                    Some(BitCount::from($value.trailing_zeros()))
                }
            );
        };
    }

    macro_rules! assert_trailing_zeros_from_digits {
        ($digits:expr) => {
            let arbi = Arbi::from_digits($digits, true);
            assert_eq!(
                arbi.trailing_zeros(),
                if arbi.is_zero() {
                    None
                } else {
                    Some(BitCount::from(
                        arbi.wrapping_to_i128().trailing_zeros(),
                    ))
                }
            );
        };
    }

    #[test]
    fn test_smoke() {
        let (mut rng, _) = get_seedable_rng();
        let die_d = get_uniform_die(Digit::MIN, Digit::MAX);

        let die_dd = get_uniform_die(Digit::MAX as DDigit + 1, DDigit::MAX);
        for _ in 0..i16::MAX {
            let digit = die_d.sample(&mut rng);
            let ddigit = die_dd.sample(&mut rng);

            assert_trailing_zeros!(digit);
            assert_trailing_zeros!(ddigit);

            assert_trailing_zeros_from_digits!(vec![0, digit]);
            assert_trailing_zeros_from_digits!(vec![
                0,
                ddigit as Digit,
                (ddigit >> Digit::BITS) as Digit
            ]);
            assert_trailing_zeros_from_digits!(vec![0, 0, digit]);
        }
    }

    #[test]
    fn test_special() {
        let zero = Arbi::zero();
        assert_eq!(zero.trailing_zeros(), None);

        let neg_one = Arbi::neg_one();
        assert_eq!(
            neg_one.trailing_zeros(),
            Some((-1_i32).trailing_zeros() as BitCount)
        );

        let one = Arbi::one();
        assert_eq!(
            one.trailing_zeros(),
            Some(1_i32.trailing_zeros() as BitCount)
        );
    }

    #[test]
    fn test_powers_of_two() {
        for i in 0..128 {
            let power_of_two = 1u128 << i;
            let arbi = Arbi::from(power_of_two);
            assert_eq!(
                arbi.trailing_zeros(),
                Some(BitCount::from(power_of_two.trailing_zeros()))
            );
        }
    }
}