malachite_base/num/logic/
bit_iterable.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::basic::signeds::PrimitiveSigned;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::num::conversion::traits::{ExactFrom, WrappingFrom};
12use crate::num::logic::traits::BitIterable;
13use core::cmp::Ordering::*;
14use core::cmp::min;
15use core::marker::PhantomData;
16use core::ops::Index;
17
18/// A double-ended iterator over the bits of an unsigned primitive integer.
19///
20/// This `struct` is created by [`BitIterable::bits`]; see its documentation for more.
21#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
22pub struct PrimitiveUnsignedBitIterator<T: PrimitiveUnsigned> {
23    pub(crate) value: T,
24    pub(crate) remaining: usize,
25    // If `n` is nonzero, this mask initially points to the least-significant bit, and is left-
26    // shifted by next().
27    pub(crate) i_mask: T,
28    // If `n` is nonzero, this mask initially points to the most-significant nonzero bit, and is
29    // right-shifted by next_back().
30    pub(crate) j_mask: T,
31}
32
33impl<T: PrimitiveUnsigned> Iterator for PrimitiveUnsignedBitIterator<T> {
34    type Item = bool;
35
36    fn next(&mut self) -> Option<bool> {
37        if self.remaining != 0 {
38            let bit = self.value & self.i_mask != T::ZERO;
39            self.i_mask <<= 1;
40            self.remaining -= 1;
41            Some(bit)
42        } else {
43            None
44        }
45    }
46
47    fn size_hint(&self) -> (usize, Option<usize>) {
48        (self.remaining, Some(self.remaining))
49    }
50}
51
52impl<T: PrimitiveUnsigned> DoubleEndedIterator for PrimitiveUnsignedBitIterator<T> {
53    fn next_back(&mut self) -> Option<bool> {
54        if self.remaining != 0 {
55            let bit = self.value & self.j_mask != T::ZERO;
56            self.j_mask >>= 1;
57            self.remaining -= 1;
58            Some(bit)
59        } else {
60            None
61        }
62    }
63}
64
65impl<T: PrimitiveUnsigned> ExactSizeIterator for PrimitiveUnsignedBitIterator<T> {}
66
67impl<T: PrimitiveUnsigned> Index<u64> for PrimitiveUnsignedBitIterator<T> {
68    type Output = bool;
69
70    /// A function to retrieve bits by index.
71    ///
72    /// The index is the power of 2 of which the bit is a coefficient. Indexing at or above the
73    /// significant bit count returns false bits.
74    ///
75    /// This is equivalent to [`get_bit`](super::traits::BitAccess::get_bit).
76    ///
77    /// # Worst-case complexity
78    /// Constant time and additional memory.
79    ///
80    /// # Examples
81    /// ```
82    /// use malachite_base::num::logic::traits::BitIterable;
83    ///
84    /// assert_eq!(0u8.bits()[0], false);
85    ///
86    /// // 105 = 1101001b
87    /// let bits = 105u32.bits();
88    /// assert_eq!(bits[0], true);
89    /// assert_eq!(bits[1], false);
90    /// assert_eq!(bits[2], false);
91    /// assert_eq!(bits[3], true);
92    /// assert_eq!(bits[4], false);
93    /// assert_eq!(bits[5], true);
94    /// assert_eq!(bits[6], true);
95    /// assert_eq!(bits[7], false);
96    /// assert_eq!(bits[100], false);
97    /// ```
98    fn index(&self, index: u64) -> &bool {
99        if self.value.get_bit(index) {
100            &true
101        } else {
102            &false
103        }
104    }
105}
106
107fn bits_unsigned<T: PrimitiveUnsigned>(x: T) -> PrimitiveUnsignedBitIterator<T> {
108    let significant_bits = x.significant_bits();
109    PrimitiveUnsignedBitIterator {
110        value: x,
111        remaining: usize::exact_from(significant_bits),
112        i_mask: T::ONE,
113        j_mask: T::power_of_2(significant_bits.saturating_sub(1)),
114    }
115}
116
117macro_rules! impl_bit_iterable_unsigned {
118    ($t:ident) => {
119        impl BitIterable for $t {
120            type BitIterator = PrimitiveUnsignedBitIterator<$t>;
121
122            /// Returns a double-ended iterator over the bits of an unsigned primitive integer.
123            ///
124            /// The forward order is ascending, so that less significant bits appear first. There
125            /// are no trailing false bits going forward, or leading falses going backward.
126            ///
127            /// If it's necessary to get a [`Vec`] of all the bits, consider using
128            /// [`to_bits_asc`](super::traits::BitConvertible::to_bits_asc) or
129            /// [`to_bits_desc`](super::traits::BitConvertible::to_bits_desc) instead.
130            ///
131            /// # Worst-case complexity
132            /// Constant time and additional memory.
133            ///
134            /// # Examples
135            /// See [here](super::bit_iterable#bits).
136            #[inline]
137            fn bits(self) -> PrimitiveUnsignedBitIterator<$t> {
138                bits_unsigned(self)
139            }
140        }
141    };
142}
143apply_to_unsigneds!(impl_bit_iterable_unsigned);
144
145/// A double-ended iterator over the bits of a signed primitive integer.
146///
147/// This `struct` is created by [`BitIterable::bits`]; see its documentation for more.
148#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
149pub struct PrimitiveSignedBitIterator<U: PrimitiveUnsigned, S: PrimitiveSigned> {
150    phantom: PhantomData<*const S>,
151    xs: PrimitiveUnsignedBitIterator<U>,
152}
153
154impl<U: PrimitiveUnsigned, S: PrimitiveSigned> Iterator for PrimitiveSignedBitIterator<U, S> {
155    type Item = bool;
156
157    #[inline]
158    fn next(&mut self) -> Option<bool> {
159        self.xs.next()
160    }
161
162    #[inline]
163    fn size_hint(&self) -> (usize, Option<usize>) {
164        self.xs.size_hint()
165    }
166}
167
168impl<U: PrimitiveUnsigned, S: PrimitiveSigned> DoubleEndedIterator
169    for PrimitiveSignedBitIterator<U, S>
170{
171    #[inline]
172    fn next_back(&mut self) -> Option<bool> {
173        self.xs.next_back()
174    }
175}
176
177impl<U: PrimitiveUnsigned, S: PrimitiveSigned> ExactSizeIterator
178    for PrimitiveSignedBitIterator<U, S>
179{
180}
181
182impl<U: PrimitiveUnsigned, S: PrimitiveSigned> Index<u64> for PrimitiveSignedBitIterator<U, S> {
183    type Output = bool;
184
185    /// A function to retrieve bits by index. The index is the power of 2 of which the bit is a
186    /// coefficient.
187    ///
188    /// Indexing at or above the significant bit count returns false or true bits, depending on the
189    /// value's sign.
190    ///
191    /// This is equivalent to [`get_bit`](super::traits::BitAccess::get_bit).
192    ///
193    /// # Worst-case complexity
194    /// Constant time and additional memory.
195    ///
196    /// # Examples
197    /// ```
198    /// use malachite_base::num::logic::traits::BitIterable;
199    ///
200    /// assert_eq!(0i8.bits()[0], false);
201    ///
202    /// // -105 = 10010111 in two's complement
203    /// let bits = (-105i32).bits();
204    /// assert_eq!(bits[0], true);
205    /// assert_eq!(bits[1], true);
206    /// assert_eq!(bits[2], true);
207    /// assert_eq!(bits[3], false);
208    /// assert_eq!(bits[4], true);
209    /// assert_eq!(bits[5], false);
210    /// assert_eq!(bits[6], false);
211    /// assert_eq!(bits[7], true);
212    /// assert_eq!(bits[100], true);
213    /// ```
214    fn index(&self, index: u64) -> &bool {
215        if self.xs[min(index, U::WIDTH - 1)] {
216            &true
217        } else {
218            &false
219        }
220    }
221}
222
223fn bits_signed<U: PrimitiveUnsigned + WrappingFrom<S>, S: PrimitiveSigned>(
224    x: S,
225) -> PrimitiveSignedBitIterator<U, S> {
226    let unsigned = U::wrapping_from(x);
227    let significant_bits = match x.sign() {
228        Equal => 0,
229        Greater => unsigned.significant_bits() + 1,
230        Less => (!unsigned).significant_bits() + 1,
231    };
232    PrimitiveSignedBitIterator {
233        phantom: PhantomData,
234        xs: PrimitiveUnsignedBitIterator {
235            value: unsigned,
236            remaining: usize::exact_from(significant_bits),
237            i_mask: U::ONE,
238            j_mask: U::power_of_2(significant_bits.saturating_sub(1)),
239        },
240    }
241}
242
243macro_rules! impl_bit_iterable_signed {
244    ($u:ident, $s:ident) => {
245        impl BitIterable for $s {
246            type BitIterator = PrimitiveSignedBitIterator<$u, $s>;
247
248            /// Returns a double-ended iterator over the bits of a signed primitive integer.
249            ///
250            /// The forward order is ascending, so that less significant bits appear first. There
251            /// are no trailing sign bits going forward, or leading sign bits going backward.
252            ///
253            /// If it's necessary to get a [`Vec`] of all the bits, consider using
254            /// [`to_bits_asc`](super::traits::BitConvertible::to_bits_asc) or
255            /// [`to_bits_desc`](super::traits::BitConvertible::to_bits_desc) instead.
256            ///
257            /// # Worst-case complexity
258            /// Constant time and additional memory.
259            ///
260            /// # Examples
261            /// See [here](super::bit_iterable#bits).
262            #[inline]
263            fn bits(self) -> PrimitiveSignedBitIterator<$u, $s> {
264                bits_signed::<$u, $s>(self)
265            }
266        }
267    };
268}
269apply_to_unsigned_signed_pairs!(impl_bit_iterable_signed);
malachite_base/num/logic/bit_iterable.rs

malachite_base/num/logic/
bit_iterable.rs
