| 1 |
use crate::Integer; |
| 2 |
use core::ops::{BitAnd, BitOr, BitXor, Shr}; |
| 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 |
/// |
| 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 |
|
| 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] |
| 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] |
| 70 |
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] |
| 76 |
pub fn average_ceil<T: Average>(x: T, y: T) -> T { |
| 77 |
x.average_ceil(&y) |
| 78 |
} |