num_primitive/unsigned.rs
1use core::convert::Infallible;
2use core::num::NonZero;
3
4use crate::{
5 NonZeroPrimitiveInteger, NonZeroPrimitiveSigned, PrimitiveInteger, PrimitiveIntegerRef,
6 PrimitiveSigned,
7};
8
9/// Trait for all primitive [unsigned integer types], including the supertraits
10/// [`PrimitiveInteger`] and [`PrimitiveNumber`][crate::PrimitiveNumber].
11///
12/// This encapsulates trait implementations and inherent methods that are common among all of the
13/// primitive unsigned integer types: [`u8`], [`u16`], [`u32`], [`u64`], [`u128`], and [`usize`].
14///
15/// See the corresponding items on the individual types for more documentation and examples.
16///
17/// This trait is sealed with a private trait to prevent downstream implementations, so we may
18/// continue to expand along with the standard library without worrying about breaking changes for
19/// implementors.
20///
21/// [unsigned integer types]: https://doc.rust-lang.org/reference/types/numeric.html#r-type.numeric.int.unsigned
22///
23/// # Examples
24///
25/// ```
26/// use num_primitive::PrimitiveUnsigned;
27///
28/// // Greatest Common Divisor (Euclidean algorithm)
29/// fn gcd<T: PrimitiveUnsigned>(mut a: T, mut b: T) -> T {
30/// let zero = T::from(0u8);
31/// while b != zero {
32/// (a, b) = (b, a % b);
33/// }
34/// a
35/// }
36///
37/// assert_eq!(gcd::<u8>(48, 18), 6);
38/// assert_eq!(gcd::<u16>(1071, 462), 21);
39/// assert_eq!(gcd::<u32>(6_700_417, 2_147_483_647), 1);
40/// ```
41pub trait PrimitiveUnsigned:
42 PrimitiveInteger
43 + core::convert::From<u8>
44 + core::convert::TryFrom<u8, Error = Infallible>
45 + core::ops::Div<Self::NonZero, Output = Self>
46 + core::ops::DivAssign<Self::NonZero>
47 + core::ops::Rem<Self::NonZero, Output = Self>
48 + core::ops::RemAssign<Self::NonZero>
49{
50 /// The signed integer type used by methods like
51 /// [`checked_add_signed`][Self::checked_add_signed].
52 type Signed: PrimitiveSigned;
53
54 /// Computes the absolute difference between `self` and `other`.
55 fn abs_diff(self, other: Self) -> Self;
56
57 /// Returns the minimum number of bits required to represent `self`.
58 /// This method returns zero if `self` is zero.
59 fn bit_width(self) -> u32;
60
61 /// Calculates `self` − `rhs` − `borrow` and returns a tuple
62 /// containing the difference and the output borrow.
63 fn borrowing_sub(self, rhs: Self, borrow: bool) -> (Self, bool);
64
65 /// Calculates `self` + `rhs` + `carry` and returns a tuple containing
66 /// the sum and the output carry (in that order).
67 fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);
68
69 /// Calculates the "full multiplication" `self * rhs + carry`
70 /// without the possibility to overflow.
71 fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);
72
73 /// Calculates the "full multiplication" `self * rhs + carry + add`.
74 fn carrying_mul_add(self, rhs: Self, carry: Self, add: Self) -> (Self, Self);
75
76 /// Returns the bit pattern of `self` reinterpreted as a signed integer of the same size.
77 fn cast_signed(self) -> Self::Signed;
78
79 /// Checked addition with a signed integer. Computes `self + rhs`, returning `None` if overflow
80 /// occurred.
81 fn checked_add_signed(self, rhs: Self::Signed) -> Option<Self>;
82
83 /// Calculates the smallest value greater than or equal to `self` that is a multiple of `rhs`.
84 /// Returns `None` if `rhs` is zero or the operation would result in overflow.
85 fn checked_next_multiple_of(self, rhs: Self) -> Option<Self>;
86
87 /// Returns the smallest power of two greater than or equal to `self`. If the next power of two
88 /// is greater than the type's maximum value, `None` is returned, otherwise the power of two is
89 /// wrapped in Some.
90 fn checked_next_power_of_two(self) -> Option<Self>;
91
92 /// Checked integer subtraction. Computes `self - rhs` and checks if the result fits into a
93 /// signed integer of the same size, returning `None` if overflow occurred.
94 fn checked_signed_diff(self, rhs: Self) -> Option<Self::Signed>;
95
96 /// Checked subtraction with a signed integer. Computes `self - rhs`,
97 /// returning `None` if overflow occurred.
98 fn checked_sub_signed(self, rhs: Self::Signed) -> Option<Self>;
99
100 /// Calculates the quotient of `self` and rhs, rounding the result towards positive infinity.
101 fn div_ceil(self, rhs: Self) -> Self;
102
103 /// Returns `true` if `self` is an integer multiple of `rhs`, and false otherwise.
104 fn is_multiple_of(self, rhs: Self) -> bool;
105
106 /// Returns `true` if and only if `self == 2^k` for some `k`.
107 fn is_power_of_two(self) -> bool;
108
109 /// Calculates the smallest value greater than or equal to `self` that is a multiple of `rhs`.
110 fn next_multiple_of(self, rhs: Self) -> Self;
111
112 /// Returns the smallest power of two greater than or equal to `self`.
113 fn next_power_of_two(self) -> Self;
114
115 /// Calculates `self + rhs` with a signed `rhs`. Returns a tuple of the addition along with a
116 /// boolean indicating whether an arithmetic overflow would occur.
117 fn overflowing_add_signed(self, rhs: Self::Signed) -> (Self, bool);
118
119 /// Calculates `self` - `rhs` with a signed `rhs`. Returns a tuple of the subtraction along
120 /// with a boolean indicating whether an arithmetic overflow would occur.
121 fn overflowing_sub_signed(self, rhs: Self::Signed) -> (Self, bool);
122
123 /// Saturating addition with a signed integer. Computes `self + rhs`, saturating at the numeric
124 /// bounds instead of overflowing.
125 fn saturating_add_signed(self, rhs: Self::Signed) -> Self;
126
127 /// Saturating integer subtraction. Computes `self` - `rhs`, saturating at
128 /// the numeric bounds instead of overflowing.
129 fn saturating_sub_signed(self, rhs: Self::Signed) -> Self;
130
131 /// Strict addition with a signed integer. Computes `self + rhs`,
132 /// panicking if overflow occurred.
133 fn strict_add_signed(self, rhs: Self::Signed) -> Self;
134
135 /// Strict subtraction with a signed integer. Computes `self - rhs`,
136 /// panicking if overflow occurred.
137 fn strict_sub_signed(self, rhs: Self::Signed) -> Self;
138
139 /// Wrapping (modular) addition with a signed integer. Computes `self + rhs`, wrapping around
140 /// at the boundary of the type.
141 fn wrapping_add_signed(self, rhs: Self::Signed) -> Self;
142
143 /// Wrapping (modular) subtraction with a signed integer. Computes
144 /// `self - rhs`, wrapping around at the boundary of the type.
145 fn wrapping_sub_signed(self, rhs: Self::Signed) -> Self;
146}
147
148/// Trait for references to primitive unsigned integer types ([`PrimitiveUnsigned`]).
149///
150/// This enables traits like the standard operators in generic code,
151/// e.g. `where &T: PrimitiveUnsignedRef<T>`.
152pub trait PrimitiveUnsignedRef<T>: PrimitiveIntegerRef<T> {}
153
154/// Trait for [`NonZero`] primitive unsigned integers, including the supertrait
155/// [`NonZeroPrimitiveInteger`].
156///
157/// This encapsulates trait implementations and inherent methods that are common among all of the
158/// implementations of `NonZero<T>`, where `T` is a [`PrimitiveUnsigned`].
159///
160/// See the corresponding items on the individual types for more documentation and examples.
161///
162/// This trait is sealed with a private trait to prevent downstream implementations, so we may
163/// continue to expand along with the standard library without worrying about breaking changes for
164/// implementors.
165///
166/// # Examples
167///
168/// ```
169/// use num_primitive::NonZeroPrimitiveUnsigned;
170/// use core::num::NonZero;
171///
172/// fn gcd<T: NonZeroPrimitiveUnsigned>(mut a: T, mut b: T) -> T {
173/// while let Some(r) = T::new(b.get() % a) {
174/// (a, b) = (r, a);
175/// }
176/// a
177/// }
178///
179/// let a = NonZero::new(48u32).unwrap();
180/// let b = NonZero::new(18u32).unwrap();
181/// assert_eq!(gcd(a, b).get(), 6);
182/// ```
183pub trait NonZeroPrimitiveUnsigned:
184 NonZeroPrimitiveInteger<Integer: PrimitiveUnsigned> + core::convert::From<NonZero<u8>>
185{
186 /// The signed non-zero integer type used by methods like
187 /// [`cast_signed`][Self::cast_signed].
188 ///
189 /// For `core::num::NonZero<T>`, this is `NonZero<T::Signed>`.
190 type NonZeroSigned: NonZeroPrimitiveSigned;
191
192 /// Returns the minimum number of bits required to represent `self`.
193 fn bit_width(self) -> NonZero<u32>;
194
195 /// Returns the bit pattern of `self` reinterpreted as a signed integer of the same size.
196 fn cast_signed(self) -> Self::NonZeroSigned;
197
198 /// Adds an unsigned integer to a non-zero value. Returns [`None`] on overflow.
199 fn checked_add(self, other: Self::Integer) -> Option<Self>;
200
201 /// Returns the smallest power of two greater than or equal to `self`. Checks for overflow and
202 /// returns [`None`] if the next power of two is greater than the type’s maximum value.
203 fn checked_next_power_of_two(self) -> Option<Self>;
204
205 /// Calculates the quotient of `self` and `rhs`, rounding the result towards positive infinity.
206 fn div_ceil(self, rhs: Self) -> Self;
207
208 /// Returns the base 10 logarithm of the number, rounded down.
209 fn ilog10(self) -> u32;
210
211 /// Returns the base 2 logarithm of the number, rounded down.
212 fn ilog2(self) -> u32;
213
214 /// Returns `true` if and only if `self == (1 << k)` for some `k`.
215 fn is_power_of_two(self) -> bool;
216
217 /// Returns the square root of the number, rounded down.
218 fn isqrt(self) -> Self;
219
220 /// Calculates the midpoint (average) between `self` and `rhs`.
221 fn midpoint(self, rhs: Self) -> Self;
222
223 /// Adds an unsigned integer to a non-zero value. Returns `Self::MAX` on overflow.
224 fn saturating_add(self, other: Self::Integer) -> Self;
225}
226
227macro_rules! impl_unsigned {
228 ($Unsigned:ident, $Signed:ty) => {
229 impl PrimitiveUnsigned for $Unsigned {
230 type Signed = $Signed;
231
232 forward! {
233 fn abs_diff(self, other: Self) -> Self;
234 fn bit_width(self) -> u32;
235 fn borrowing_sub(self, rhs: Self, borrow: bool) -> (Self, bool);
236 fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);
237 fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);
238 fn carrying_mul_add(self, rhs: Self, carry: Self, add: Self) -> (Self, Self);
239 fn cast_signed(self) -> Self::Signed;
240 fn checked_add_signed(self, rhs: Self::Signed) -> Option<Self>;
241 fn checked_next_multiple_of(self, rhs: Self) -> Option<Self>;
242 fn checked_next_power_of_two(self) -> Option<Self>;
243 fn checked_signed_diff(self, rhs: Self) -> Option<Self::Signed>;
244 fn checked_sub_signed(self, rhs: Self::Signed) -> Option<Self>;
245 fn div_ceil(self, rhs: Self) -> Self;
246 fn is_multiple_of(self, rhs: Self) -> bool;
247 fn is_power_of_two(self) -> bool;
248 fn next_multiple_of(self, rhs: Self) -> Self;
249 fn next_power_of_two(self) -> Self;
250 fn overflowing_add_signed(self, rhs: Self::Signed) -> (Self, bool);
251 fn overflowing_sub_signed(self, rhs: Self::Signed) -> (Self, bool);
252 fn saturating_add_signed(self, rhs: Self::Signed) -> Self;
253 fn saturating_sub_signed(self, rhs: Self::Signed) -> Self;
254 fn strict_add_signed(self, rhs: Self::Signed) -> Self;
255 fn strict_sub_signed(self, rhs: Self::Signed) -> Self;
256 fn wrapping_add_signed(self, rhs: Self::Signed) -> Self;
257 fn wrapping_sub_signed(self, rhs: Self::Signed) -> Self;
258 }
259 }
260
261 impl PrimitiveUnsignedRef<$Unsigned> for &$Unsigned {}
262
263 impl NonZeroPrimitiveUnsigned for NonZero<$Unsigned> {
264 type NonZeroSigned = NonZero<$Signed>;
265
266 forward! {
267 fn bit_width(self) -> NonZero<u32>;
268 fn cast_signed(self) -> Self::NonZeroSigned;
269 fn checked_add(self, other: Self::Integer) -> Option<Self>;
270 fn checked_next_power_of_two(self) -> Option<Self>;
271 fn div_ceil(self, rhs: Self) -> Self;
272 fn ilog10(self) -> u32;
273 fn ilog2(self) -> u32;
274 fn is_power_of_two(self) -> bool;
275 fn isqrt(self) -> Self;
276 fn midpoint(self, rhs: Self) -> Self;
277 fn saturating_add(self, other: Self::Integer) -> Self;
278 }
279 }
280 };
281}
282
283impl_unsigned!(u8, i8);
284impl_unsigned!(u16, i16);
285impl_unsigned!(u32, i32);
286impl_unsigned!(u64, i64);
287impl_unsigned!(u128, i128);
288impl_unsigned!(usize, isize);