malachite_base/num/logic/
significant_bits.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::arithmetic::traits::UnsignedAbs;
10use crate::num::basic::signeds::PrimitiveSigned;
11use crate::num::basic::unsigneds::PrimitiveUnsigned;
12use crate::num::logic::traits::{LeadingZeros, SignificantBits};
13
14fn significant_bits_unsigned<T: PrimitiveUnsigned>(x: T) -> u64 {
15    T::WIDTH - LeadingZeros::leading_zeros(x)
16}
17
18macro_rules! impl_significant_bits_unsigned {
19    ($t:ident) => {
20        impl SignificantBits for $t {
21            /// Returns the number of significant bits of an unsigned primitive integer.
22            ///
23            /// This is the integer's width minus the number of leading zeros.
24            ///
25            /// $$
26            /// f(n) = \\begin{cases}
27            ///     0 & \text{if} \\quad n = 0, \\\\
28            ///     \lfloor \log_2 n \rfloor + 1 & \text{if} \\quad n > 0.
29            /// \\end{cases}
30            /// $$
31            ///
32            /// # Worst-case complexity
33            /// Constant time and additional memory.
34            ///
35            /// # Examples
36            /// See [here](super::significant_bits#significant_bits).
37            #[inline]
38            fn significant_bits(self) -> u64 {
39                significant_bits_unsigned(self)
40            }
41        }
42    };
43}
44apply_to_unsigneds!(impl_significant_bits_unsigned);
45
46fn significant_bits_signed<U: PrimitiveUnsigned, S: PrimitiveSigned + UnsignedAbs<Output = U>>(
47    x: S,
48) -> u64 {
49    x.unsigned_abs().significant_bits()
50}
51
52macro_rules! impl_significant_bits_signed {
53    ($u:ident, $s:ident) => {
54        /// Returns the number of significant bits of a signed primitive integer.
55        ///
56        /// This is the integer's width minus the number of leading zeros of its absolute value.
57        ///
58        /// $$
59        /// f(n) = \\begin{cases}
60        ///     0 & \text{if} \\quad n = 0, \\\\
61        ///     \lfloor \log_2 |n| \rfloor + 1 & \text{if} \\quad n \neq 0.
62        /// \\end{cases}
63        /// $$
64        ///
65        /// # Worst-case complexity
66        /// Constant time and additional memory.
67        ///
68        /// # Examples
69        /// See [here](super::significant_bits#significant_bits).
70        impl SignificantBits for $s {
71            #[inline]
72            fn significant_bits(self) -> u64 {
73                significant_bits_signed(self)
74            }
75        }
76    };
77}
78apply_to_unsigned_signed_pairs!(impl_significant_bits_signed);
malachite_base/num/logic/significant_bits.rs

malachite_base/num/logic/
significant_bits.rs
