num_primitive/unsigned.rs
1use core::convert::Infallible;
2
3use crate::{PrimitiveInteger, PrimitiveIntegerRef, PrimitiveSigned};
4
5/// Trait for all primitive [unsigned integer types], including the supertraits
6/// [`PrimitiveInteger`] and [`PrimitiveNumber`][crate::PrimitiveNumber].
7///
8/// This encapsulates trait implementations and inherent methods that are common among all of the
9/// primitive unsigned integer types: [`u8`], [`u16`], [`u32`], [`u64`], [`u128`], and [`usize`].
10///
11/// See the corresponding items on the individual types for more documentation and examples.
12///
13/// This trait is sealed with a private trait to prevent downstream implementations, so we may
14/// continue to expand along with the standard library without worrying about breaking changes for
15/// implementors.
16///
17/// [unsigned integer types]: https://doc.rust-lang.org/reference/types/numeric.html#r-type.numeric.int.unsigned
18///
19/// # Examples
20///
21/// ```
22/// use num_primitive::PrimitiveUnsigned;
23///
24/// // Greatest Common Divisor (Euclidean algorithm)
25/// fn gcd<T: PrimitiveUnsigned>(mut a: T, mut b: T) -> T {
26/// let zero = T::from(0u8);
27/// while b != zero {
28/// (a, b) = (b, a % b);
29/// }
30/// a
31/// }
32///
33/// assert_eq!(gcd::<u8>(48, 18), 6);
34/// assert_eq!(gcd::<u16>(1071, 462), 21);
35/// assert_eq!(gcd::<u32>(6_700_417, 2_147_483_647), 1);
36/// ```
37pub trait PrimitiveUnsigned: PrimitiveInteger + From<u8> + TryFrom<u8, Error = Infallible> {
38 /// The signed integer type used by methods like
39 /// [`checked_add_signed`][Self::checked_add_signed].
40 type Signed: PrimitiveSigned;
41
42 /// Computes the absolute difference between `self` and `other`.
43 fn abs_diff(self, other: Self) -> Self;
44
45 /// Calculates `self` − `rhs` − `borrow` and returns a tuple
46 /// containing the difference and the output borrow.
47 fn borrowing_sub(self, rhs: Self, borrow: bool) -> (Self, bool);
48
49 /// Calculates `self` + `rhs` + `carry` and returns a tuple containing
50 /// the sum and the output carry (in that order).
51 fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);
52
53 /// Calculates the "full multiplication" `self * rhs + carry`
54 /// without the possibility to overflow.
55 fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);
56
57 /// Calculates the "full multiplication" `self * rhs + carry + add`.
58 fn carrying_mul_add(self, rhs: Self, carry: Self, add: Self) -> (Self, Self);
59
60 /// Returns the bit pattern of `self` reinterpreted as a signed integer of the same size.
61 fn cast_signed(self) -> Self::Signed;
62
63 /// Checked addition with a signed integer. Computes `self + rhs`, returning `None` if overflow
64 /// occurred.
65 fn checked_add_signed(self, rhs: Self::Signed) -> Option<Self>;
66
67 /// Calculates the smallest value greater than or equal to `self` that is a multiple of `rhs`.
68 /// Returns `None` if `rhs` is zero or the operation would result in overflow.
69 fn checked_next_multiple_of(self, rhs: Self) -> Option<Self>;
70
71 /// Returns the smallest power of two greater than or equal to `self`. If the next power of two
72 /// is greater than the type's maximum value, `None` is returned, otherwise the power of two is
73 /// wrapped in Some.
74 fn checked_next_power_of_two(self) -> Option<Self>;
75
76 /// Checked integer subtraction. Computes `self - rhs` and checks if the result fits into a
77 /// signed integer of the same size, returning `None` if overflow occurred.
78 fn checked_signed_diff(self, rhs: Self) -> Option<Self::Signed>;
79
80 /// Checked subtraction with a signed integer. Computes `self - rhs`,
81 /// returning `None` if overflow occurred.
82 fn checked_sub_signed(self, rhs: Self::Signed) -> Option<Self>;
83
84 /// Calculates the quotient of `self` and rhs, rounding the result towards positive infinity.
85 fn div_ceil(self, rhs: Self) -> Self;
86
87 /// Returns `true` if `self` is an integer multiple of `rhs`, and false otherwise.
88 fn is_multiple_of(self, rhs: Self) -> bool;
89
90 /// Returns `true` if and only if `self == 2^k` for some `k`.
91 fn is_power_of_two(self) -> bool;
92
93 /// Calculates the smallest value greater than or equal to `self` that is a multiple of `rhs`.
94 fn next_multiple_of(self, rhs: Self) -> Self;
95
96 /// Returns the smallest power of two greater than or equal to `self`.
97 fn next_power_of_two(self) -> Self;
98
99 /// Calculates `self + rhs` with a signed `rhs`. Returns a tuple of the addition along with a
100 /// boolean indicating whether an arithmetic overflow would occur.
101 fn overflowing_add_signed(self, rhs: Self::Signed) -> (Self, bool);
102
103 /// Calculates `self` - `rhs` with a signed `rhs`. Returns a tuple of the subtraction along
104 /// with a boolean indicating whether an arithmetic overflow would occur.
105 fn overflowing_sub_signed(self, rhs: Self::Signed) -> (Self, bool);
106
107 /// Saturating addition with a signed integer. Computes `self + rhs`, saturating at the numeric
108 /// bounds instead of overflowing.
109 fn saturating_add_signed(self, rhs: Self::Signed) -> Self;
110
111 /// Saturating integer subtraction. Computes `self` - `rhs`, saturating at
112 /// the numeric bounds instead of overflowing.
113 fn saturating_sub_signed(self, rhs: Self::Signed) -> Self;
114
115 /// Strict addition with a signed integer. Computes `self + rhs`,
116 /// panicking if overflow occurred.
117 fn strict_add_signed(self, rhs: Self::Signed) -> Self;
118
119 /// Strict subtraction with a signed integer. Computes `self - rhs`,
120 /// panicking if overflow occurred.
121 fn strict_sub_signed(self, rhs: Self::Signed) -> Self;
122
123 /// Wrapping (modular) addition with a signed integer. Computes `self + rhs`, wrapping around
124 /// at the boundary of the type.
125 fn wrapping_add_signed(self, rhs: Self::Signed) -> Self;
126
127 /// Wrapping (modular) subtraction with a signed integer. Computes
128 /// `self - rhs`, wrapping around at the boundary of the type.
129 fn wrapping_sub_signed(self, rhs: Self::Signed) -> Self;
130}
131
132/// Trait for references to primitive unsigned integer types ([`PrimitiveUnsigned`]).
133///
134/// This enables traits like the standard operators in generic code,
135/// e.g. `where &T: PrimitiveUnsignedRef<T>`.
136pub trait PrimitiveUnsignedRef<T>: PrimitiveIntegerRef<T> {}
137
138macro_rules! impl_unsigned {
139 ($Unsigned:ident, $Signed:ty) => {
140 impl PrimitiveUnsigned for $Unsigned {
141 type Signed = $Signed;
142
143 forward! {
144 fn abs_diff(self, other: Self) -> Self;
145 fn borrowing_sub(self, rhs: Self, borrow: bool) -> (Self, bool);
146 fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);
147 fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);
148 fn carrying_mul_add(self, rhs: Self, carry: Self, add: Self) -> (Self, Self);
149 fn cast_signed(self) -> Self::Signed;
150 fn checked_add_signed(self, rhs: Self::Signed) -> Option<Self>;
151 fn checked_next_multiple_of(self, rhs: Self) -> Option<Self>;
152 fn checked_next_power_of_two(self) -> Option<Self>;
153 fn checked_signed_diff(self, rhs: Self) -> Option<Self::Signed>;
154 fn checked_sub_signed(self, rhs: Self::Signed) -> Option<Self>;
155 fn div_ceil(self, rhs: Self) -> Self;
156 fn is_multiple_of(self, rhs: Self) -> bool;
157 fn is_power_of_two(self) -> bool;
158 fn next_multiple_of(self, rhs: Self) -> Self;
159 fn next_power_of_two(self) -> Self;
160 fn overflowing_add_signed(self, rhs: Self::Signed) -> (Self, bool);
161 fn overflowing_sub_signed(self, rhs: Self::Signed) -> (Self, bool);
162 fn saturating_add_signed(self, rhs: Self::Signed) -> Self;
163 fn saturating_sub_signed(self, rhs: Self::Signed) -> Self;
164 fn strict_add_signed(self, rhs: Self::Signed) -> Self;
165 fn strict_sub_signed(self, rhs: Self::Signed) -> Self;
166 fn wrapping_add_signed(self, rhs: Self::Signed) -> Self;
167 fn wrapping_sub_signed(self, rhs: Self::Signed) -> Self;
168 }
169 }
170
171 impl PrimitiveUnsignedRef<$Unsigned> for &$Unsigned {}
172 };
173}
174
175impl_unsigned!(u8, i8);
176impl_unsigned!(u16, i16);
177impl_unsigned!(u32, i32);
178impl_unsigned!(u64, i64);
179impl_unsigned!(u128, i128);
180impl_unsigned!(usize, isize);