1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
use super::core; /// Computes bit reversal by going bit by bit and setting the reverse position bit for the output. pub trait BitwiseReverse<T> { /// Swaps the bits such that bit i is now bit N-i, where N is the length of the T in bits. fn swap_bits(self) -> T; } macro_rules! doit_bitwise { ($($ty:ty),*) => ($( impl BitwiseReverse<$ty> for $ty { // This algorithm uses the reverse variable as a like a stack to reverse the value. // The lesser significant bits are pushed onto the reverse variable and then the variable // is shifted down to make room for more significant bits. This algorithm has a shortcut, // that if there aren't anymore 1s to push onto the reverse variable the algorithm ends // early and shift the reverse to the correct position. #[inline] fn swap_bits(self) -> $ty { let mut v = self; // By initializing the reversal to value, we have already loaded the largest // significant bit into the correct location. let mut r = self; // Compute how many bits are left to shift at the end of the algorithm. let mut s = 8 * core::mem::size_of::<$ty>() - 1; v >>= 1; while v != 0 { // Quit early if there are no more 1s to shift in r <<= 1; // Make room for the next significant bit r |= v & 1; // Add the bit to the reverse variable v >>= 1; // Go to the next significant bit s -= 1; // Decrement the leftover bit count } // Shift the reversal to the correct position and return the reversal return r << s; } })*) } doit_bitwise!(u8, u16, u32, u64, usize); doit_signed!(BitwiseReverse); test_suite!();