1 
//! Utilities for working with numbers, particularly powers of two.
2 

            

        

            

                3
            

            

                
            

            

                
/// Returns true when the given value is a power of two.

            

        

            

                4
            

            

                
            

            

                
///

            

        

            

                5
            

            

                
            

            

                
/// A number is a power of two when exactly a single bit is one.

            

        

            

                6
            

            

                28
            

            

                
pub fn is_power_of_two<T>(value: T) -> bool

            

        

            

                7
            

            

                28
            

            

                
where

            

        

            

                8
            

            

                28
            

            

                
    T: num::PrimInt,

            

        

            

                9
            

            

                
            

            

                
{

            

        

            

                10
            

            

                28
            

            

                
    !value.is_zero() && (value & (value - T::one())).is_zero()

            

        

            

                11
            

            

                28
            

            

                
}

            

        

            

                12
            

            

                
            

            

                

            

        

            

                13
            

            

                
            

            

                
/// Returns the smallest power of two that is larger than or equal to the given

            

        

            

                14
            

            

                
            

            

                
/// value.

            

        

            

                15
            

            

                
            

            

                
///

            

        

            

                16
            

            

                
            

            

                
/// # Panics

            

        

            

                17
            

            

                
            

            

                
///

            

        

            

                18
            

            

                
            

            

                
/// This function will panic if the value is larger than the largest power of

            

        

            

                19
            

            

                
            

            

                
/// two that can be represented by the type `T`.

            

        

            

                20
            

            

                
            

            

                
///

            

        

            

                21
            

            

                
            

            

                
/// # Examples

            

        

            

                22
            

            

                
            

            

                
/// ```

            

        

            

                23
            

            

                
            

            

                
/// use merc_number::round_up_to_power_of_two;

            

        

            

                24
            

            

                
            

            

                
///

            

        

            

                25
            

            

                
            

            

                
/// assert_eq!(round_up_to_power_of_two(3u32), 4);

            

        

            

                26
            

            

                
            

            

                
/// assert_eq!(round_up_to_power_of_two(4u32), 4);

            

        

            

                27
            

            

                
            

            

                
/// assert_eq!(round_up_to_power_of_two(5u32), 8);

            

        

            

                28
            

            

                
            

            

                
/// ```

            

        

            

                29
            

            

                14
            

            

                
pub fn round_up_to_power_of_two<T>(value: T) -> T

            

        

            

                30
            

            

                14
            

            

                
where

            

        

            

                31
            

            

                14
            

            

                
    T: num::PrimInt,

            

        

            

                32
            

            

                
            

            

                
{

            

        

            

                33
            

            

                14
            

            

                
    if value.is_zero() {

            

        

            

                34
            

            

                1
            

            

                
        return T::one();

            

        

            

                35
            

            

                13
            

            

                
    }

            

        

            

                36
            

            

                
            

            

                

            

        

            

                37
            

            

                13
            

            

                
    if is_power_of_two(value) {

            

        

            

                38
            

            

                4
            

            

                
        return value;

            

        

            

                39
            

            

                9
            

            

                
    }

            

        

            

                40
            

            

                
            

            

                

            

        

            

                41
            

            

                9
            

            

                
    let bits = std::mem::size_of::<T>() * 8;

            

        

            

                42
            

            

                9
            

            

                
    T::one() << (bits - value.leading_zeros() as usize)

            

        

            

                43
            

            

                14
            

            

                
}

            

        

            

                44
            

            

                
            

            

                

            

        

            

                45
            

            

                
            

            

                
#[cfg(test)]

            

        

            

                46
            

            

                
            

            

                
mod tests {

            

        

            

                47
            

            

                
            

            

                
    use super::*;

            

        

            

                48
            

            

                
            

            

                

            

        

            

                49
            

            

                
            

            

                
    #[test]

            

        

            

                50
            

            

                1
            

            

                
    fn test_is_power_of_two() {

            

        

            

                51
            

            

                
            

            

                
        // Test powers of 2

            

        

            

                52
            

            

                1
            

            

                
        assert!(is_power_of_two(1u32));

            

        

            

                53
            

            

                1
            

            

                
        assert!(is_power_of_two(2u32));

            

        

            

                54
            

            

                1
            

            

                
        assert!(is_power_of_two(4u32));

            

        

            

                55
            

            

                1
            

            

                
        assert!(is_power_of_two(8u32));

            

        

            

                56
            

            

                1
            

            

                
        assert!(is_power_of_two(16u32));

            

        

            

                57
            

            

                
            

            

                

            

        

            

                58
            

            

                
            

            

                
        // Test non-powers of 2

            

        

            

                59
            

            

                1
            

            

                
        assert!(!is_power_of_two(0u32));

            

        

            

                60
            

            

                1
            

            

                
        assert!(!is_power_of_two(3u32));

            

        

            

                61
            

            

                1
            

            

                
        assert!(!is_power_of_two(5u32));

            

        

            

                62
            

            

                1
            

            

                
        assert!(!is_power_of_two(6u32));

            

        

            

                63
            

            

                1
            

            

                
        assert!(!is_power_of_two(7u32));

            

        

            

                64
            

            

                1
            

            

                
    }

            

        

            

                65
            

            

                
            

            

                

            

        

            

                66
            

            

                
            

            

                
    #[test]

            

        

            

                67
            

            

                1
            

            

                
    fn test_round_up_to_power_of_two() {

            

        

            

                68
            

            

                
            

            

                
        // Test exact powers of 2

            

        

            

                69
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(1u32), 1);

            

        

            

                70
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(2u32), 2);

            

        

            

                71
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(4u32), 4);

            

        

            

                72
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(8u32), 8);

            

        

            

                73
            

            

                
            

            

                

            

        

            

                74
            

            

                
            

            

                
        // Test values in between

            

        

            

                75
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(0u32), 1);

            

        

            

                76
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(3u32), 4);

            

        

            

                77
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(5u32), 8);

            

        

            

                78
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(7u32), 8);

            

        

            

                79
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(9u32), 16);

            

        

            

                80
            

            

                1
            

            

                
    }

            

        

            

                81
            

            

                
            

            

                

            

        

            

                82
            

            

                
            

            

                
    #[test]

            

        

            

                83
            

            

                1
            

            

                
    fn test_different_types() {

            

        

            

                84
            

            

                1
            

            

                
        assert!(is_power_of_two(4u8));

            

        

            

                85
            

            

                1
            

            

                
        assert!(is_power_of_two(8u16));

            

        

            

                86
            

            

                1
            

            

                
        assert!(is_power_of_two(16u32));

            

        

            

                87
            

            

                1
            

            

                
        assert!(is_power_of_two(32u64));

            

        

            

                88
            

            

                1
            

            

                
        assert!(is_power_of_two(64usize));

            

        

            

                89
            

            

                
            

            

                

            

        

            

                90
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(3u8), 4);

            

        

            

                91
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(5u16), 8);

            

        

            

                92
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(9u32), 16);

            

        

            

                93
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(17u64), 32);

            

        

            

                94
            

            

                1
            

            

                
        assert_eq!(round_up_to_power_of_two(33usize), 64);

            

        

            

                95
            

            

                1
            

            

                
    }

            

        

            

                96
            

            

                
            

            

                
}