num_integer/
average.rs

Help
1use core::ops::{BitAnd, BitOr, BitXor, Shr};
2use Integer;
3
4/// Provides methods to compute the average of two integers, without overflows.
5pub 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    ///
23    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    ///
42    fn average_floor(&self, other: &Self) -> Self;
43}
44
45impl<I> Average for I
46where
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]
56    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]
62    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]
70pub 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]
76pub fn average_ceil<T: Average>(x: T, y: T) -> T {
77    x.average_ceil(&y)
78}
num_integer/average.rs

num_integer/
average.rs
