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

use crate::{
    ibig::IBig,
    primitive::{Word, WORD_BITS},
    ubig::{Repr::*, UBig},
};

impl UBig {
    /// Returns the number of trailing zeros in the binary representation.
    ///
    /// In other words, it is the smallest `n` such that 2 to the power of `n` divides the number.
    ///
    /// For 0, it returns `None`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ibig::ubig;
    /// assert_eq!(ubig!(17).trailing_zeros(), Some(0));
    /// assert_eq!(ubig!(48).trailing_zeros(), Some(4));
    /// assert_eq!(ubig!(0b101000000).trailing_zeros(), Some(6));
    /// assert_eq!(ubig!(0).trailing_zeros(), None);
    /// ```
    #[inline]
    pub fn trailing_zeros(&self) -> Option<usize> {
        match self.repr() {
            Small(0) => None,
            Small(word) => Some(word.trailing_zeros() as usize),
            Large(buffer) => Some(trailing_zeros_large(buffer)),
        }
    }

    /// Integer logarithm base 2.
    ///
    /// Returns the floor of the logarithm base 2 of the number.
    /// In other words, it is the position of the highest 1 bit in the binary representation.
    ///
    /// For 0, it returns `None`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ibig::ubig;
    /// assert_eq!(ubig!(17).ilog2(), Some(4));
    /// assert_eq!(ubig!(0b101000000).ilog2(), Some(8));
    /// assert_eq!(ubig!(0).ilog2(), None);
    /// ```
    #[inline]
    pub fn ilog2(&self) -> Option<usize> {
        match self.repr() {
            Small(0) => None,
            Small(word) => Some((WORD_BITS - 1 - word.leading_zeros()) as usize),
            Large(buffer) => Some(
                buffer.len() * WORD_BITS as usize
                    - 1
                    - buffer.last().unwrap().leading_zeros() as usize,
            ),
        }
    }
}

fn trailing_zeros_large(words: &[Word]) -> usize {
    debug_assert!(*words.last().unwrap() != 0);

    for (idx, word) in words.iter().enumerate() {
        if *word != 0 {
            return idx * WORD_BITS as usize + word.trailing_zeros() as usize;
        }
    }
    panic!("trailing_zeros_large(0)")
}

impl IBig {
    /// Returns the number of trailing zeros in the two's complement binary representation.
    ///
    /// In other words, it is the smallest `n` such that 2 to the power of `n` divides the number.
    ///
    /// For 0, it returns `None`.
    ///
    /// # Examples
    ///
    /// ```
    /// # use ibig::ibig;
    /// assert_eq!(ibig!(17).trailing_zeros(), Some(0));
    /// assert_eq!(ibig!(-48).trailing_zeros(), Some(4));
    /// assert_eq!(ibig!(-0b101000000).trailing_zeros(), Some(6));
    /// assert_eq!(ibig!(0).trailing_zeros(), None);
    /// ```
    #[inline]
    pub fn trailing_zeros(&self) -> Option<usize> {
        self.magnitude().trailing_zeros()
    }
}