malachite_nz/natural/logic/bit_scan.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// Uses code adopted from the GNU MP Library.
4//
5// Copyright © 2000-2002, 2004, 2012, 2015 Free Software Foundation, Inc.
6//
7// This file is part of Malachite.
8//
9// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
10// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
11// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
12
13use crate::natural::InnerNatural::{Large, Small};
14use crate::natural::{Natural, bit_to_limb_count_floor, limb_to_bit_count};
15use crate::platform::Limb;
16use malachite_base::num::basic::integers::PrimitiveInt;
17use malachite_base::num::logic::traits::{BitScan, TrailingZeros};
18use malachite_base::slices::slice_leading_zeros;
19
20// Interpreting a slice of `Limb`s as the limbs (in ascending order) of a `Natural`, finds the
21// lowest index greater than or equal to `start` at which the `Natural` has a `false` bit.
22//
23// # Worst-case complexity
24// $T(n) = O(n)$
25//
26// $M(n) = O(1)$
27//
28// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
29//
30// This is equivalent to `mpn_scan0` from `mpn/generic/scan0.c`, GMP 6.2.1.
31pub_crate_test! {limbs_index_of_next_false_bit(xs: &[Limb], start: u64) -> u64 {
32 let starting_index = bit_to_limb_count_floor(start);
33 if starting_index >= xs.len() {
34 return start;
35 }
36 if let Some(result) = xs[starting_index].index_of_next_false_bit(start & Limb::WIDTH_MASK)
37 && result != Limb::WIDTH
38 {
39 return limb_to_bit_count(starting_index) + result;
40 }
41 if starting_index == xs.len() - 1 {
42 return limb_to_bit_count(xs.len());
43 }
44 let false_index = starting_index
45 + 1
46 + xs[starting_index + 1..]
47 .iter()
48 .take_while(|&&y| y == Limb::MAX)
49 .count();
50 let mut result_offset = limb_to_bit_count(false_index);
51 if false_index != xs.len() {
52 result_offset += TrailingZeros::trailing_zeros(!xs[false_index]);
53 }
54 result_offset
55}}
56
57// Interpreting a slice of `Limb`s as the limbs (in ascending order) of a `Natural`, finds the
58// lowest index greater than or equal to `start` at which the `Natural` has a `true` bit. If the
59// starting index is too large and there are no more `true` bits above it, `None` is returned.
60//
61// # Worst-case complexity
62// $T(n) = O(n)$
63//
64// $M(n) = O(1)$
65//
66// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
67//
68// This is equivalent to `mpn_scan1` from `mpn/generic/scan1.c`, GMP 6.2.1.
69pub_crate_test! {limbs_index_of_next_true_bit(xs: &[Limb], start: u64) -> Option<u64> {
70 let starting_index = bit_to_limb_count_floor(start);
71 if starting_index >= xs.len() {
72 None
73 } else if let Some(result) = xs[starting_index].index_of_next_true_bit(start & Limb::WIDTH_MASK)
74 {
75 Some(limb_to_bit_count(starting_index) + result)
76 } else if starting_index == xs.len() - 1 {
77 None
78 } else {
79 let true_index = starting_index + 1 + slice_leading_zeros(&xs[starting_index + 1..]);
80 if true_index == xs.len() {
81 None
82 } else {
83 let result_offset = limb_to_bit_count(true_index);
84 Some(
85 result_offset
86 .checked_add(TrailingZeros::trailing_zeros(xs[true_index]))
87 .unwrap(),
88 )
89 }
90 }
91}}
92
93impl BitScan for &Natural {
94 /// Given a [`Natural`] and a starting index, searches the [`Natural`] for the smallest index of
95 /// a `false` bit that is greater than or equal to the starting index.
96 ///
97 /// Since every [`Natural`] has an implicit prefix of infinitely-many zeros, this function
98 /// always returns a value.
99 ///
100 /// Starting beyond the [`Natural`]'s width is allowed; the result is the starting index.
101 ///
102 /// # Worst-case complexity
103 /// $T(n) = O(n)$
104 ///
105 /// $M(n) = O(1)$
106 ///
107 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
108 ///
109 /// # Examples
110 /// ```
111 /// use malachite_base::num::logic::traits::BitScan;
112 /// use malachite_nz::natural::Natural;
113 ///
114 /// assert_eq!(
115 /// Natural::from(0xb00000000u64).index_of_next_false_bit(0),
116 /// Some(0)
117 /// );
118 /// assert_eq!(
119 /// Natural::from(0xb00000000u64).index_of_next_false_bit(20),
120 /// Some(20)
121 /// );
122 /// assert_eq!(
123 /// Natural::from(0xb00000000u64).index_of_next_false_bit(31),
124 /// Some(31)
125 /// );
126 /// assert_eq!(
127 /// Natural::from(0xb00000000u64).index_of_next_false_bit(32),
128 /// Some(34)
129 /// );
130 /// assert_eq!(
131 /// Natural::from(0xb00000000u64).index_of_next_false_bit(33),
132 /// Some(34)
133 /// );
134 /// assert_eq!(
135 /// Natural::from(0xb00000000u64).index_of_next_false_bit(34),
136 /// Some(34)
137 /// );
138 /// assert_eq!(
139 /// Natural::from(0xb00000000u64).index_of_next_false_bit(35),
140 /// Some(36)
141 /// );
142 /// assert_eq!(
143 /// Natural::from(0xb00000000u64).index_of_next_false_bit(100),
144 /// Some(100)
145 /// );
146 /// ```
147 fn index_of_next_false_bit(self, start: u64) -> Option<u64> {
148 match self {
149 Natural(Small(small)) => small.index_of_next_false_bit(start),
150 Natural(Large(limbs)) => Some(limbs_index_of_next_false_bit(limbs, start)),
151 }
152 }
153
154 /// Given a [`Natural`] and a starting index, searches the [`Natural`] for the smallest index of
155 /// a `true` bit that is greater than or equal to the starting index.
156 ///
157 /// If the starting index is greater than or equal to the [`Natural`]'s width, the result is
158 /// `None` since there are no `true` bits past that point.
159 ///
160 /// # Worst-case complexity
161 /// $T(n) = O(n)$
162 ///
163 /// $M(n) = O(1)$
164 ///
165 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
166 ///
167 /// # Examples
168 /// ```
169 /// use malachite_base::num::logic::traits::BitScan;
170 /// use malachite_nz::natural::Natural;
171 ///
172 /// assert_eq!(
173 /// Natural::from(0xb00000000u64).index_of_next_true_bit(0),
174 /// Some(32)
175 /// );
176 /// assert_eq!(
177 /// Natural::from(0xb00000000u64).index_of_next_true_bit(20),
178 /// Some(32)
179 /// );
180 /// assert_eq!(
181 /// Natural::from(0xb00000000u64).index_of_next_true_bit(31),
182 /// Some(32)
183 /// );
184 /// assert_eq!(
185 /// Natural::from(0xb00000000u64).index_of_next_true_bit(32),
186 /// Some(32)
187 /// );
188 /// assert_eq!(
189 /// Natural::from(0xb00000000u64).index_of_next_true_bit(33),
190 /// Some(33)
191 /// );
192 /// assert_eq!(
193 /// Natural::from(0xb00000000u64).index_of_next_true_bit(34),
194 /// Some(35)
195 /// );
196 /// assert_eq!(
197 /// Natural::from(0xb00000000u64).index_of_next_true_bit(35),
198 /// Some(35)
199 /// );
200 /// assert_eq!(
201 /// Natural::from(0xb00000000u64).index_of_next_true_bit(36),
202 /// None
203 /// );
204 /// assert_eq!(
205 /// Natural::from(0xb00000000u64).index_of_next_true_bit(100),
206 /// None
207 /// );
208 /// ```
209 fn index_of_next_true_bit(self, start: u64) -> Option<u64> {
210 match self {
211 Natural(Small(small)) => small.index_of_next_true_bit(start),
212 Natural(Large(limbs)) => limbs_index_of_next_true_bit(limbs, start),
213 }
214 }
215}