malachite_nz/natural/logic/
significant_bits.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// Uses code adopted from the GNU MP Library.
4//
5//      Copyright © 1991, 1993-1995, 2001, 2002 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;
15use malachite_base::num::basic::unsigneds::PrimitiveUnsigned;
16use malachite_base::num::conversion::traits::WrappingFrom;
17use malachite_base::num::logic::traits::SignificantBits;
18
19// Interpreting a slice of `Limb`s as the limbs of a `Natural` in ascending order, returns the
20// smallest number of bits necessary to represent that `Natural`. 0 has zero significant bits. When
21// the `Natural` is nonzero, this is equal to 1 + floor(log<sub>2</sub>(`self`)).
22//
23// This function assumes that `xs` is nonempty and the last (most significant) limb is nonzero.
24//
25// # Worst-case complexity
26// Constant time and additional memory.
27//
28// # Panics
29// Panics if `xs` is empty.
30//
31// This is equivalent to `mpz_sizeinbase` from `mpz/sizeinbase.c`, GMP 6.2.1, where `x` is
32// non-negative and `base` is 2.
33pub_crate_test! {limbs_significant_bits<T: PrimitiveUnsigned>(xs: &[T]) -> u64 {
34    ((u64::wrapping_from(xs.len()) - 1) << T::LOG_WIDTH) + xs.last().unwrap().significant_bits()
35}}
36
37impl SignificantBits for &Natural {
38    /// Returns the number of significant bits of a [`Natural`].
39    ///
40    /// $$
41    /// f(n) = \\begin{cases}
42    ///     0 & \text{if} \\quad n = 0, \\\\
43    ///     \lfloor \log_2 n \rfloor + 1 & \text{if} \\quad n > 0.
44    /// \\end{cases}
45    /// $$
46    ///
47    /// # Worst-case complexity
48    /// Constant time and additional memory.
49    ///
50    /// # Examples
51    /// ```
52    /// use malachite_base::num::basic::traits::Zero;
53    /// use malachite_base::num::logic::traits::SignificantBits;
54    /// use malachite_nz::natural::Natural;
55    ///
56    /// assert_eq!(Natural::ZERO.significant_bits(), 0);
57    /// assert_eq!(Natural::from(100u32).significant_bits(), 7);
58    /// ```
59    fn significant_bits(self) -> u64 {
60        match self {
61            Natural(Small(small)) => small.significant_bits(),
62            Natural(Large(limbs)) => limbs_significant_bits(limbs),
63        }
64    }
65}
malachite_nz/natural/logic/significant_bits.rs

malachite_nz/natural/logic/
significant_bits.rs
