1 use core::ops::{BitAnd, BitOr, BitXor, Shr};
2 use Integer;
3
4 /// Provides methods to compute the average of two integers, without overflows.
5 pub trait Average: Integer {
6 /// Returns the ceiling value of the average of `self` and `other`.
7 /// -- `⌈(self + other)/2⌉`
8 ///
9 /// # Examples
10 ///
11 /// ```
12 /// use num_integer::Average;
13 ///
14 /// assert_eq!(( 3).average_ceil(&10), 7);
15 /// assert_eq!((-2).average_ceil(&-5), -3);
16 /// assert_eq!(( 4).average_ceil(& 4), 4);
17 ///
18 /// assert_eq!(u8::max_value().average_ceil(&2), 129);
19 /// assert_eq!(i8::min_value().average_ceil(&-1), -64);
20 /// assert_eq!(i8::min_value().average_ceil(&i8::max_value()), 0);
21 /// ```
22 ///
average_ceil(&self, other: &Self) -> Self23 fn average_ceil(&self, other: &Self) -> Self;
24
25 /// Returns the floor value of the average of `self` and `other`.
26 /// -- `⌊(self + other)/2⌋`
27 ///
28 /// # Examples
29 ///
30 /// ```
31 /// use num_integer::Average;
32 ///
33 /// assert_eq!(( 3).average_floor(&10), 6);
34 /// assert_eq!((-2).average_floor(&-5), -4);
35 /// assert_eq!(( 4).average_floor(& 4), 4);
36 ///
37 /// assert_eq!(u8::max_value().average_floor(&2), 128);
38 /// assert_eq!(i8::min_value().average_floor(&-1), -65);
39 /// assert_eq!(i8::min_value().average_floor(&i8::max_value()), -1);
40 /// ```
41 ///
average_floor(&self, other: &Self) -> Self42 fn average_floor(&self, other: &Self) -> Self;
43 }
44
45 impl<I> Average for I
46 where
47 I: Integer + Shr<usize, Output = I>,
48 for<'a, 'b> &'a I:
49 BitAnd<&'b I, Output = I> + BitOr<&'b I, Output = I> + BitXor<&'b I, Output = I>,
50 {
51 // The Henry Gordon Dietz implementation as shown in the Hacker's Delight,
52 // see http://aggregate.org/MAGIC/#Average%20of%20Integers
53
54 /// Returns the floor value of the average of `self` and `other`.
55 #[inline]
average_floor(&self, other: &I) -> I56 fn average_floor(&self, other: &I) -> I {
57 (self & other) + ((self ^ other) >> 1)
58 }
59
60 /// Returns the ceil value of the average of `self` and `other`.
61 #[inline]
average_ceil(&self, other: &I) -> I62 fn average_ceil(&self, other: &I) -> I {
63 (self | other) - ((self ^ other) >> 1)
64 }
65 }
66
67 /// Returns the floor value of the average of `x` and `y` --
68 /// see [Average::average_floor](trait.Average.html#tymethod.average_floor).
69 #[inline]
average_floor<T: Average>(x: T, y: T) -> T70 pub fn average_floor<T: Average>(x: T, y: T) -> T {
71 x.average_floor(&y)
72 }
73 /// Returns the ceiling value of the average of `x` and `y` --
74 /// see [Average::average_ceil](trait.Average.html#tymethod.average_ceil).
75 #[inline]
average_ceil<T: Average>(x: T, y: T) -> T76 pub fn average_ceil<T: Average>(x: T, y: T) -> T {
77 x.average_ceil(&y)
78 }
79