malachite_nz/integer/logic/
checked_count_zeros.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::integer::Integer;
10use crate::natural::InnerNatural::{Large, Small};
11use crate::natural::Natural;
12use crate::platform::Limb;
13use malachite_base::num::basic::integers::PrimitiveInt;
14use malachite_base::num::logic::traits::{CountOnes, CountZeros};
15
16// Interpreting a slice of `Limb`s, as the limbs (in ascending order) of a `Natural`, counts the
17// number of zeros in the binary expansion of the negative (two's complement) of the `Natural`.
18// `limbs` cannot be empty.
19//
20// # Worst-case complexity
21// $T(n) = O(n)$
22//
23// $M(n) = O(1)$
24//
25// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
26pub_crate_test! {limbs_count_zeros_neg(xs: &[Limb]) -> u64 {
27    let mut sum = 0;
28    let mut nonzero_seen = false;
29    for &x in xs {
30        sum += if nonzero_seen {
31            CountOnes::count_ones(x)
32        } else if x == 0 {
33            Limb::WIDTH
34        } else {
35            nonzero_seen = true;
36            CountZeros::count_zeros(x.wrapping_neg())
37        };
38    }
39    sum
40}}
41
42impl Natural {
43    fn count_zeros_neg(&self) -> u64 {
44        match self {
45            Natural(Small(small)) => CountZeros::count_zeros(small.wrapping_neg()),
46            Natural(Large(limbs)) => limbs_count_zeros_neg(limbs),
47        }
48    }
49}
50
51impl Integer {
52    /// Counts the number of zeros in the binary expansion of an [`Integer`]. If the [`Integer`] is
53    /// non-negative, then the number of zeros is infinite, so `None` is returned.
54    ///
55    /// # Worst-case complexity
56    /// $T(n) = O(n)$
57    ///
58    /// $M(n) = O(1)$
59    ///
60    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
61    ///
62    /// # Examples
63    /// ```
64    /// use malachite_base::num::arithmetic::traits::Pow;
65    /// use malachite_base::num::basic::traits::Zero;
66    /// use malachite_nz::integer::Integer;
67    ///
68    /// assert_eq!(Integer::ZERO.checked_count_zeros(), None);
69    /// // -105 = 10010111 in two's complement
70    /// assert_eq!(Integer::from(-105).checked_count_zeros(), Some(3));
71    /// assert_eq!(Integer::from(105).checked_count_zeros(), None);
72    /// // -10^12 = 10001011100101011010110101111000000000000 in two's complement
73    /// assert_eq!(
74    ///     (-Integer::from(10u32).pow(12)).checked_count_zeros(),
75    ///     Some(24)
76    /// );
77    /// ```
78    pub fn checked_count_zeros(&self) -> Option<u64> {
79        if self.sign {
80            None
81        } else {
82            Some(self.abs.count_zeros_neg())
83        }
84    }
85}
malachite_nz/integer/logic/checked_count_zeros.rs

malachite_nz/integer/logic/
checked_count_zeros.rs
