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