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
use crate::integer::Integer;
use crate::natural::InnerNatural::{Large, Small};
use crate::natural::Natural;
use crate::platform::Limb;
use malachite_base::num::basic::integers::PrimitiveInt;
use malachite_base::num::logic::traits::{CountOnes, CountZeros};
// Interpreting a slice of `Limb`s, as the limbs (in ascending order) of a `Natural`, counts the
// number of zeros in the binary expansion of the negative (two's complement) of the `Natural`.
// `limbs` cannot be empty.
//
// # Worst-case complexity
// $T(n) = O(n)$
//
// $M(n) = O(1)$
//
// where $T$ is time, $M$ is additional memory, and $n$ is `xs.len()`.
pub_crate_test! {limbs_count_zeros_neg(xs: &[Limb]) -> u64 {
let mut sum = 0;
let mut nonzero_seen = false;
for &x in xs.iter() {
sum += if nonzero_seen {
CountOnes::count_ones(x)
} else if x == 0 {
Limb::WIDTH
} else {
nonzero_seen = true;
CountZeros::count_zeros(x.wrapping_neg())
};
}
sum
}}
impl Natural {
fn count_zeros_neg(&self) -> u64 {
match *self {
Natural(Small(small)) => CountZeros::count_zeros(small.wrapping_neg()),
Natural(Large(ref limbs)) => limbs_count_zeros_neg(limbs),
}
}
}
impl Integer {
/// Counts the number of zeros in the binary expansion of an [`Integer`]. If the [`Integer`] is
/// non-negative, then the number of zeros is infinite, so `None` is returned.
///
/// # Worst-case complexity
/// $T(n) = O(n)$
///
/// $M(n) = O(1)$
///
/// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
///
/// # Examples
/// ```
/// extern crate malachite_base;
///
/// use malachite_base::num::arithmetic::traits::Pow;
/// use malachite_base::num::basic::traits::Zero;
/// use malachite_nz::integer::Integer;
///
/// assert_eq!(Integer::ZERO.checked_count_zeros(), None);
/// // -105 = 10010111 in two's complement
/// assert_eq!(Integer::from(-105).checked_count_zeros(), Some(3));
/// assert_eq!(Integer::from(105).checked_count_zeros(), None);
/// // -10^12 = 10001011100101011010110101111000000000000 in two's complement
/// assert_eq!((-Integer::from(10u32).pow(12)).checked_count_zeros(), Some(24));
/// ```
pub fn checked_count_zeros(&self) -> Option<u64> {
if self.sign {
None
} else {
Some(self.abs.count_zeros_neg())
}
}
}