gcd_bitwise/
interface.rs

1use std::cmp::min;
2use std::convert::{TryFrom, TryInto};
3use std::fmt::Debug;
4use std::mem::swap;
5use std::ops::{ShlAssign, ShrAssign, SubAssign};
6/// # Examples
7///
8/// ```
9/// use gcd_bitwise::interface::gcd;
10///
11/// fn main() {
12///     let num1: u8 = 15;
13///
14///     let num2: u8 = 51;
15///     
16///     let gcd = gcd(num1, num2);
17///     
18///     println!("gcd: {}", gcd); // 3   
19/// }
20pub fn gcd<T>(mut num1: T, mut num2: T) -> T
21where
22    T: Copy
23        + PartialEq
24        + PartialOrd
25        + ShrAssign
26        + ShlAssign
27        + SubAssign
28        + TryFrom<usize>
29        + TryInto<usize>,
30    <T as TryFrom<usize>>::Error: Debug,
31    <T as TryInto<usize>>::Error: Debug,
32{
33    if num1.try_into().unwrap() == 0 {
34        return num2;
35    } else if num2.try_into().unwrap() == 0 {
36        return num1;
37    }
38
39    let min_twos = {
40        let twos_num1 = num1.try_into()
41                                    .unwrap()
42                                    .trailing_zeros() as usize;
43
44        let twos_num2 = num2.try_into()
45                                    .unwrap()
46                                    .trailing_zeros() as usize;
47
48        num1 >>= T::try_from(twos_num1).unwrap();
49        num2 >>= T::try_from(twos_num2).unwrap();
50
51        min(twos_num1, twos_num2)
52    };
53
54    loop {
55        if num1 > num2 {
56            swap(&mut num1, &mut num2);
57        }
58
59        num2 -= num1;
60
61        if num2.try_into().unwrap() == 0 {
62            num1 <<= T::try_from(min_twos).unwrap();
63            return num1;
64        }
65
66        num1 >>= T::try_from(num1.try_into()
67                                    .unwrap()
68                                    .trailing_zeros() as usize)
69                                    .unwrap();
70    }
71}
gcd_bitwise/interface.rs

gcd_bitwise/
interface.rs
