sync_utils/
bithacks.rs

1//! bithacks functions.
2//!
3//! Implemented according to paper "Faster Remainder by Direct Computation Applications to Compilers and Software Libraries".
4
5/// Given a 32-bit number, find the highest bit number which is set 1.
6///
7/// For example:
8///
9/// ``` text
10///   for 0011(3), returns 1.
11///   for 0100(4), returns 2.
12/// ```
13#[inline]
14pub fn highest_bit_set(n: u32) -> u32 {
15    let mut c: u32 = 0;
16    let mut _n = n;
17    if _n >= 65536 {
18        _n >>= 16;
19        c += 16;
20    }
21    if _n >= 256 {
22        _n >>= 8;
23        c += 8;
24    }
25    if _n >= 16 {
26        _n >>= 4;
27        c += 4;
28    }
29    if _n >= 4 {
30        _n >>= 2;
31        c += 2;
32    }
33    if _n >= 2 { c + 1 } else { c }
34}
35
36/// Given a 32-bit number, return the next highest power of 2, and the corresponding shift.
37///
38/// For example:
39///
40/// ``` text
41///    if n is 7, then function will return (8, 3), which 8 = 1 << 3
42/// ```
43#[inline]
44pub fn round_up_to_power2(n: u32) -> (u32, u32) {
45    let mut _n = n;
46    _n -= 1;
47    _n |= _n >> 1;
48    _n |= _n >> 2;
49    _n |= _n >> 4;
50    _n |= _n >> 8;
51    _n |= _n >> 16;
52    _n += 1;
53    (_n, highest_bit_set(_n))
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_highest_bit_set() {
62        assert_eq!(highest_bit_set(1), 0);
63        assert_eq!(highest_bit_set(3), 1);
64        assert_eq!(highest_bit_set(4), 2);
65        assert_eq!(highest_bit_set(33554432), 25);
66        assert_eq!(highest_bit_set(1615855616), 30);
67    }
68
69    #[test]
70    fn test_round_up_to_power2() {
71        assert_eq!(round_up_to_power2(1), (1, 0));
72        assert_eq!(round_up_to_power2(3), (4, 2));
73        assert_eq!(round_up_to_power2(4), (4, 2));
74        assert_eq!(round_up_to_power2(5), (8, 3));
75        assert_eq!(round_up_to_power2(100), (128, 7));
76        assert_eq!(round_up_to_power2(16 * 1024 - 100), (16 * 1024, 14));
77    }
78}
sync_utils/bithacks.rs

sync_utils/
bithacks.rs
