malachite_base/num/logic/
bit_scan.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::logic::traits::{BitScan, TrailingZeros};
12
13fn index_of_next_false_bit_unsigned<T: PrimitiveUnsigned>(x: T, start: u64) -> u64 {
14    if start >= T::WIDTH {
15        start
16    } else {
17        TrailingZeros::trailing_zeros(!(x | T::low_mask(start)))
18    }
19}
20
21fn index_of_next_true_bit_unsigned<T: PrimitiveUnsigned>(x: T, start: u64) -> Option<u64> {
22    if start >= T::WIDTH {
23        None
24    } else {
25        let index = TrailingZeros::trailing_zeros(x & !T::low_mask(start));
26        if index == T::WIDTH { None } else { Some(index) }
27    }
28}
29
30macro_rules! impl_bit_scan_unsigned {
31    ($t:ident) => {
32        impl BitScan for $t {
33            /// Given a number and a starting index, searches the number for the smallest index of a
34            /// `false` bit that is greater than or equal to the starting index.
35            ///
36            /// Since the number is unsigned and therefore has an implicit prefix of infinitely-many
37            /// zeros, this function always returns a value.
38            ///
39            /// Starting beyond the type's width is allowed; the result is the starting index.
40            ///
41            /// # Worst-case complexity
42            /// Constant time and additional memory.
43            ///
44            /// # Examples
45            /// See [here](super::bit_scan#index_of_next_false_bit).
46            #[inline]
47            fn index_of_next_false_bit(self, start: u64) -> Option<u64> {
48                Some(index_of_next_false_bit_unsigned(self, start))
49            }
50
51            /// Given a number and a starting index, searches the number for the smallest index of a
52            /// `true` bit that is greater than or equal to the starting index.
53            ///
54            /// If the starting index is greater than or equal to the type's width, the result is
55            /// `None` since there are no `true` bits past that point.
56            ///
57            /// # Worst-case complexity
58            /// Constant time and additional memory.
59            ///
60            /// # Examples
61            /// See [here](super::bit_scan#index_of_next_true_bit).
62            #[inline]
63            fn index_of_next_true_bit(self, start: u64) -> Option<u64> {
64                index_of_next_true_bit_unsigned(self, start)
65            }
66        }
67    };
68}
69apply_to_unsigneds!(impl_bit_scan_unsigned);
70
71fn index_of_next_false_bit_signed<T: PrimitiveSigned>(x: T, start: u64) -> Option<u64> {
72    if start >= T::WIDTH - 1 {
73        if x >= T::ZERO { Some(start) } else { None }
74    } else {
75        let index = TrailingZeros::trailing_zeros(!(x | T::low_mask(start)));
76        if index == T::WIDTH { None } else { Some(index) }
77    }
78}
79
80fn index_of_next_true_bit_signed<T: PrimitiveSigned>(x: T, start: u64) -> Option<u64> {
81    if start >= T::WIDTH - 1 {
82        if x >= T::ZERO { None } else { Some(start) }
83    } else {
84        let index = TrailingZeros::trailing_zeros(x & !T::low_mask(start));
85        if index == T::WIDTH { None } else { Some(index) }
86    }
87}
88
89macro_rules! impl_bit_scan_signed {
90    ($t:ident) => {
91        impl BitScan for $t {
92            /// Given a number and a starting index, searches the number for the smallest index of a
93            /// `false` bit that is greater than or equal to the starting index.
94            ///
95            /// If the starting index is greater than or equal to the type's width, then the result
96            /// depends on whether the number is negative. If it is, then the result is `None` since
97            /// there are no `false` bits past that point. If the number is non-negative, then the
98            /// result is the starting index.
99            ///
100            /// # Worst-case complexity
101            /// Constant time and additional memory.
102            ///
103            /// # Examples
104            /// See [here](super::bit_scan#index_of_next_false_bit).
105            #[inline]
106            fn index_of_next_false_bit(self, start: u64) -> Option<u64> {
107                index_of_next_false_bit_signed(self, start)
108            }
109
110            /// Given a number and a starting index, searches the number for the smallest index of a
111            /// `true` bit that is greater than or equal to the starting index.
112            ///
113            /// If the starting index is greater than or equal to the type's width, then the result
114            /// depends on whether the number is non-negative. If it is, then the result is `None`
115            /// since there are no `true` bits past that point. If the number is negative, then the
116            /// result is the starting index.
117            ///
118            /// # Worst-case complexity
119            /// Constant time and additional memory.
120            ///
121            /// # Examples
122            /// See [here](super::bit_scan#index_of_next_true_bit).
123            #[inline]
124            fn index_of_next_true_bit(self, start: u64) -> Option<u64> {
125                index_of_next_true_bit_signed(self, start)
126            }
127        }
128    };
129}
130apply_to_signeds!(impl_bit_scan_signed);
malachite_base/num/logic/bit_scan.rs

malachite_base/num/logic/
bit_scan.rs
