```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
```
``````use core::ops::{BitAnd, BitOr, BitXor, Shr};
use Integer;

/// Provides methods to compute the average of two integers, without overflows.
pub trait Average: Integer {
/// Returns the ceiling value of the average of `self` and `other`.
/// -- `⌈(self + other)/2⌉`
///
/// # Examples
///
/// ```
/// use num_integer::Average;
///
/// assert_eq!(( 3).average_ceil(&10),  7);
/// assert_eq!((-2).average_ceil(&-5), -3);
/// assert_eq!(( 4).average_ceil(& 4),  4);
///
/// assert_eq!(u8::max_value().average_ceil(&2), 129);
/// assert_eq!(i8::min_value().average_ceil(&-1), -64);
/// assert_eq!(i8::min_value().average_ceil(&i8::max_value()), 0);
/// ```
///
fn average_ceil(&self, other: &Self) -> Self;

/// Returns the floor value of the average of `self` and `other`.
/// -- `⌊(self + other)/2⌋`
///
/// # Examples
///
/// ```
/// use num_integer::Average;
///
/// assert_eq!(( 3).average_floor(&10),  6);
/// assert_eq!((-2).average_floor(&-5), -4);
/// assert_eq!(( 4).average_floor(& 4),  4);
///
/// assert_eq!(u8::max_value().average_floor(&2), 128);
/// assert_eq!(i8::min_value().average_floor(&-1), -65);
/// assert_eq!(i8::min_value().average_floor(&i8::max_value()), -1);
/// ```
///
fn average_floor(&self, other: &Self) -> Self;
}

impl<I> Average for I
where
I: Integer + Shr<usize, Output = I>,
for<'a, 'b> &'a I:
BitAnd<&'b I, Output = I> + BitOr<&'b I, Output = I> + BitXor<&'b I, Output = I>,
{
// The Henry Gordon Dietz implementation as shown in the Hacker's Delight,
// see http://aggregate.org/MAGIC/#Average%20of%20Integers

/// Returns the floor value of the average of `self` and `other`.
#[inline]
fn average_floor(&self, other: &I) -> I {
(self & other) + ((self ^ other) >> 1)
}

/// Returns the ceil value of the average of `self` and `other`.
#[inline]
fn average_ceil(&self, other: &I) -> I {
(self | other) - ((self ^ other) >> 1)
}
}

/// Returns the floor value of the average of `x` and `y` --
/// see [Average::average_floor](trait.Average.html#tymethod.average_floor).
#[inline]
pub fn average_floor<T: Average>(x: T, y: T) -> T {
x.average_floor(&y)
}
/// Returns the ceiling value of the average of `x` and `y` --
/// see [Average::average_ceil](trait.Average.html#tymethod.average_ceil).
#[inline]
pub fn average_ceil<T: Average>(x: T, y: T) -> T {
x.average_ceil(&y)
}
``````