malachite_nz/natural/arithmetic/mod_power_of_2_is_reduced.rs
1// Copyright © 2026 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::natural::Natural;
10use malachite_base::num::arithmetic::traits::ModPowerOf2IsReduced;
11use malachite_base::num::logic::traits::SignificantBits;
12
13impl ModPowerOf2IsReduced for Natural {
14 /// Returns whether a [`Natural`] is reduced modulo 2^k$; in other words, whether it has no more
15 /// than $k$ significant bits.
16 ///
17 /// $f(x, k) = (x < 2^k)$.
18 ///
19 /// # Worst-case complexity
20 /// Constant time and additional memory.
21 ///
22 /// # Examples
23 /// ```
24 /// use malachite_base::num::arithmetic::traits::{ModPowerOf2IsReduced, Pow};
25 /// use malachite_base::num::basic::traits::Zero;
26 /// use malachite_nz::natural::Natural;
27 ///
28 /// assert_eq!(Natural::ZERO.mod_power_of_2_is_reduced(5), true);
29 /// assert_eq!(
30 /// Natural::from(10u32).pow(12).mod_power_of_2_is_reduced(39),
31 /// false
32 /// );
33 /// assert_eq!(
34 /// Natural::from(10u32).pow(12).mod_power_of_2_is_reduced(40),
35 /// true
36 /// );
37 /// ```
38 #[inline]
39 fn mod_power_of_2_is_reduced(&self, pow: u64) -> bool {
40 self.significant_bits() <= pow
41 }
42}