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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
use crate::Uint;
// FEATURE: Special functions
// * Factorial
// * Extended GCD and LCM
// * https://en.wikipedia.org/wiki/Euler%27s_totient_function
// * https://en.wikipedia.org/wiki/Carmichael_function
// * https://en.wikipedia.org/wiki/Jordan%27s_totient_function
// * Feature parity with GMP:
// * https://gmplib.org/manual/Integer-Functions.html#Integer-Functions
// https://en.wikipedia.org/wiki/Kronecker_symbol
// Subsumes Jacobi and Legendre symbols.
// Primality testing
// https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases
impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS> {
/// Returns `true` if and only if `self == 2^k` for some `k`.
#[inline]
#[must_use]
pub const fn is_power_of_two(self) -> bool {
self.count_ones() == 1
}
/// Returns the smallest power of two greater than or equal to self.
///
/// # Panics
///
/// Panics if the value overlfows.
#[inline]
#[must_use]
pub const fn next_power_of_two(self) -> Self {
self.checked_next_power_of_two().unwrap()
}
/// Returns the smallest power of two greater than or equal to `self`. If
/// the next power of two is greater than the type’s maximum value,
/// [`None`] is returned, otherwise the power of two is wrapped in
/// [`Some`].
///
/// # Examples
///
/// ```
/// # use ruint::{Uint, uint, aliases::U64};
/// # uint!{
/// assert_eq!(0_U64.checked_next_power_of_two(), Some(1_U64));
/// assert_eq!(1_U64.checked_next_power_of_two(), Some(1_U64));
/// assert_eq!(2_U64.checked_next_power_of_two(), Some(2_U64));
/// assert_eq!(3_U64.checked_next_power_of_two(), Some(4_U64));
/// assert_eq!(U64::MAX.checked_next_power_of_two(), None);
/// # }
/// ```
#[inline]
#[must_use]
pub const fn checked_next_power_of_two(self) -> Option<Self> {
self.one_less_than_next_power_of_two()
.checked_add(Self::ONE)
}
const fn one_less_than_next_power_of_two(self) -> Self {
if self.const_is_zero() || self.const_eq(&Self::ONE) {
return Self::ZERO;
}
let p = self.wrapping_sub(Self::ONE);
let z = p.leading_zeros();
Self::MAX.wrapping_shr(z)
}
/// Calculates the smallest value greater than or equal to self that is a
/// multiple of rhs.
///
/// # Panics
///
/// This function will panic if `rhs` is 0 or the operation results in
/// overflow.
#[inline]
#[must_use]
#[track_caller]
pub fn next_multiple_of(self, rhs: Self) -> Self {
let r = self % rhs;
if r.is_zero() {
self
} else {
// rhs - r cannot overflow because r is smaller than rhs
self.checked_add(rhs - r).unwrap()
}
}
/// Calculates the smallest value greater than or equal to `self` that is a
/// multiple of `rhs`. Returns [`None`] is `rhs` is zero or the
/// operation would result in overflow.
///
/// # Examples
///
/// ```
/// # use ruint::{Uint, uint, aliases::U64};
/// # uint!{
/// assert_eq!(16_U64.checked_next_multiple_of(8_U64), Some(16_U64));
/// assert_eq!(23_U64.checked_next_multiple_of(8_U64), Some(24_U64));
/// assert_eq!(1_U64.checked_next_multiple_of(0_U64), None);
/// assert_eq!(U64::MAX.checked_next_multiple_of(2_U64), None);
/// # }
/// ```
///
/// ```
/// # use ruint::{Uint, uint};
/// # uint!{
/// assert_eq!(0_U0.checked_next_multiple_of(0_U0), None);
/// assert_eq!(0_U1.checked_next_multiple_of(0_U1), None);
/// assert_eq!(0_U1.checked_next_multiple_of(1_U1), Some(0_U1));
/// assert_eq!(1_U1.checked_next_multiple_of(0_U1), None);
/// assert_eq!(1_U1.checked_next_multiple_of(1_U1), Some(1_U1));
/// # }
/// ```
#[inline]
#[must_use]
pub fn checked_next_multiple_of(self, rhs: Self) -> Option<Self> {
let r = self.checked_rem(rhs)?;
if r.is_zero() {
Some(self)
} else {
// rhs - r cannot overflow because r is smaller than rhs
self.checked_add(rhs - r)
}
}
}