pub fn ones(n: u16) -> u128 {
0_u128.wrapping_sub(1) >> (128 - n)
}
pub fn parse_int(s: &str) -> Result<u128, core::num::ParseIntError> {
let mut chars = s.chars();
if chars.next() == Some('0') {
if chars.next() == Some('x') {
let res = chars.collect::<String>();
return u128::from_str_radix(&res, 16);
} else if chars.next().is_some() {
panic!("other bases not supported");
}
}
let signed: i128 = s.parse()?;
Ok(signed as _)
}
pub fn reverse(mut x: u128, n: u16) -> u128 {
match n {
1 => x & 1,
2 => ((x >> 1) & 1) + ((x << 1) & 2),
3..=4 => {
x = ((x >> 2) & 3) + ((x << 2) & 0xc);
x = ((x >> 1) & 5) + ((x << 1) & 0xa);
x >> (4 - n)
}
5..=8 => {
x = ((x >> 4) & 0x0f) + ((x << 4) & 0xf0);
x = ((x >> 2) & 0x33) + ((x << 2) & 0xcc);
x = ((x >> 1) & 0x55) + ((x << 1) & 0xaa);
x >> (8 - n)
}
9..=16 => {
x = ((x >> 8) & 0x00ff) + ((x << 8) & 0xff00);
x = ((x >> 4) & 0x0f0f) + ((x << 4) & 0xf0f0);
x = ((x >> 2) & 0x3333) + ((x << 2) & 0xcccc);
x = ((x >> 1) & 0x5555) + ((x << 1) & 0xaaaa);
x >> (16 - n)
}
17..=32 => {
x = ((x >> 16) & 0x0000ffff) + ((x << 16) & 0xffff0000);
x = ((x >> 8) & 0x00ff00ff) + ((x << 8) & 0xff00ff00);
x = ((x >> 4) & 0x0f0f0f0f) + ((x << 4) & 0xf0f0f0f0);
x = ((x >> 2) & 0x33333333) + ((x << 2) & 0xcccccccc);
x = ((x >> 1) & 0x55555555) + ((x << 1) & 0xaaaaaaaa);
x >> (32 - n)
}
33..=64 => {
x = ((x >> 32) & 0x00000000ffffffff) + ((x << 32) & 0xffffffff00000000);
x = ((x >> 16) & 0x0000ffff0000ffff) + ((x << 16) & 0xffff0000ffff0000);
x = ((x >> 8) & 0x00ff00ff00ff00ff) + ((x << 8) & 0xff00ff00ff00ff00);
x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) + ((x << 4) & 0xf0f0f0f0f0f0f0f0);
x = ((x >> 2) & 0x3333333333333333) + ((x << 2) & 0xcccccccccccccccc);
x = ((x >> 1) & 0x5555555555555555) + ((x << 1) & 0xaaaaaaaaaaaaaaaa);
x >> (64 - n)
}
65..=128 => {
let hi = reverse(x, 64) << (n - 64);
let lo = reverse(x >> 64, n - 64);
lo | hi
}
_ => panic!("Bitwidth must be less than 128!"),
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn reverse_one_bit() {
assert_eq!(0, reverse(0, 1));
assert_eq!(1, reverse(1, 1));
}
#[test]
fn reverse_two_bits() {
assert_eq!(0b00, reverse(0b00, 2));
assert_eq!(0b10, reverse(0b01, 2));
assert_eq!(0b01, reverse(0b10, 2));
assert_eq!(0b11, reverse(0b11, 2));
}
#[test]
fn reverse_three_bits() {
assert_eq!(0b000, reverse(0b000, 3));
assert_eq!(0b100, reverse(0b001, 3));
assert_eq!(0b010, reverse(0b010, 3));
assert_eq!(0b110, reverse(0b011, 3));
assert_eq!(0b001, reverse(0b100, 3));
assert_eq!(0b101, reverse(0b101, 3));
assert_eq!(0b011, reverse(0b110, 3));
assert_eq!(0b111, reverse(0b111, 3));
}
#[test]
fn reverse_four_bits() {
assert_eq!(0b0000, reverse(0b0000, 4));
assert_eq!(0b1000, reverse(0b0001, 4));
assert_eq!(0b0100, reverse(0b0010, 4));
assert_eq!(0b1100, reverse(0b0011, 4));
assert_eq!(0b0010, reverse(0b0100, 4));
assert_eq!(0b1010, reverse(0b0101, 4));
assert_eq!(0b0110, reverse(0b0110, 4));
assert_eq!(0b1110, reverse(0b0111, 4));
assert_eq!(0b0001, reverse(0b1000, 4));
assert_eq!(0b1001, reverse(0b1001, 4));
assert_eq!(0b0101, reverse(0b1010, 4));
assert_eq!(0b1101, reverse(0b1011, 4));
assert_eq!(0b0011, reverse(0b1100, 4));
assert_eq!(0b1011, reverse(0b1101, 4));
assert_eq!(0b0111, reverse(0b1110, 4));
assert_eq!(0b1111, reverse(0b1111, 4));
}
#[test]
fn reverse_five_bits() {
assert_eq!(0b10101, reverse(0b10101, 5));
assert_eq!(0b10100, reverse(0b00101, 5));
assert_eq!(0b00101, reverse(0b10100, 5));
assert_eq!(0b10001, reverse(0b10001, 5));
assert_eq!(0b11101, reverse(0b10111, 5));
assert_eq!(0b10111, reverse(0b11101, 5));
}
#[test]
fn reverse_six_bits() {
assert_eq!(0b010101, reverse(0b101010, 6));
assert_eq!(0b010100, reverse(0b001010, 6));
assert_eq!(0b000101, reverse(0b101000, 6));
assert_eq!(0b100010, reverse(0b010001, 6));
assert_eq!(0b111010, reverse(0b010111, 6));
assert_eq!(0b101110, reverse(0b011101, 6));
}
#[test]
fn reverse_seven_bits() {
assert_eq!(0b0010101, reverse(0b1010100, 7));
assert_eq!(0b0010100, reverse(0b0010100, 7));
assert_eq!(0b1000101, reverse(0b1010001, 7));
assert_eq!(0b1100010, reverse(0b0100011, 7));
assert_eq!(0b1110100, reverse(0b0010111, 7));
assert_eq!(0b1011100, reverse(0b0011101, 7));
}
#[test]
fn reverse_eight_bits() {
assert_eq!(0b00010101, reverse(0b10101000, 8));
assert_eq!(0b10010100, reverse(0b00101001, 8));
assert_eq!(0b01000101, reverse(0b10100010, 8));
assert_eq!(0b11100010, reverse(0b01000111, 8));
assert_eq!(0b01110100, reverse(0b00101110, 8));
assert_eq!(0b11011100, reverse(0b00111011, 8));
}
#[test]
fn reverse_nine_bits() {
assert_eq!(0b000101011, reverse(0b110101000, 9));
assert_eq!(0b100101001, reverse(0b100101001, 9));
assert_eq!(0b010001011, reverse(0b110100010, 9));
assert_eq!(0b111000101, reverse(0b101000111, 9));
assert_eq!(0b011101001, reverse(0b100101110, 9));
assert_eq!(0b110111001, reverse(0b100111011, 9));
}
#[test]
fn reverse_sixteen_bits() {
assert_eq!(0b1000010101110101, reverse(0b1010111010100001, 16));
assert_eq!(0b1010010100110101, reverse(0b1010110010100101, 16));
assert_eq!(0b1001000101110101, reverse(0b1010111010001001, 16));
assert_eq!(0b1011100010110101, reverse(0b1010110100011101, 16));
assert_eq!(0b1001110100110101, reverse(0b1010110010111001, 16));
assert_eq!(0b1011011100110101, reverse(0b1010110011101101, 16));
}
#[test]
fn reverse_seventeen_bits() {
assert_eq!(0b10100010101110101, reverse(0b10101110101000101, 17));
assert_eq!(0b10010010100110101, reverse(0b10101100101001001, 17));
assert_eq!(0b10101000101110101, reverse(0b10101110100010101, 17));
assert_eq!(0b10011100010110101, reverse(0b10101101000111001, 17));
assert_eq!(0b10101110100110101, reverse(0b10101100101110101, 17));
assert_eq!(0b10011011100110101, reverse(0b10101100111011001, 17));
}
#[test]
fn reverse_thirty_two_bits() {
assert_eq!(
0b01000101011101011000010101110101,
reverse(0b10101110101000011010111010100010, 32)
);
assert_eq!(
0b10100101001101011010010100110101,
reverse(0b10101100101001011010110010100101, 32)
);
assert_eq!(
0b01010001011101011001000101110101,
reverse(0b10101110100010011010111010001010, 32)
);
assert_eq!(
0b10111000101101011011100010110101,
reverse(0b10101101000111011010110100011101, 32)
);
assert_eq!(
0b01011101001101011001110100110101,
reverse(0b10101100101110011010110010111010, 32)
);
assert_eq!(
0b10110111001101011011011100110101,
reverse(0b10101100111011011010110011101101, 32)
);
}
#[test]
fn reverse_thirty_three_bits() {
assert_eq!(
0b101000101011101011000010101110101,
reverse(0b101011101010000110101110101000101, 33)
);
assert_eq!(
0b010100101001101011010010100110101,
reverse(0b101011001010010110101100101001010, 33)
);
assert_eq!(
0b101010001011101011001000101110101,
reverse(0b101011101000100110101110100010101, 33)
);
assert_eq!(
0b010111000101101011011100010110101,
reverse(0b101011010001110110101101000111010, 33)
);
assert_eq!(
0b101011101001101011001110100110101,
reverse(0b101011001011100110101100101110101, 33)
);
assert_eq!(
0b010110111001101011011011100110101,
reverse(0b101011001110110110101100111011010, 33)
);
}
#[test]
fn reverse_sixty_four_bits() {
assert_eq!(0xf0f0f0f0f0f0f0f0, reverse(0x0f0f0f0f0f0f0f0f, 64));
assert_eq!(0x3535353535353535, reverse(0xacacacacacacacac, 64));
}
#[test]
fn reverse_sixty_five_bits() {
assert_eq!(0x10000000000000000, reverse(1, 65));
assert_eq!(0x1f0f0f0f0f0f0f0f0, reverse(0x01e1e1e1e1e1e1e1f, 65));
}
#[test]
fn reverse_one_hundred_twenty_eight_bits() {
assert_eq!(0x80000000000000000000000000000000, reverse(1, 128));
assert_eq!(
0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0,
reverse(0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f, 128)
);
assert_eq!(
0x35353535353535353535353535353535,
reverse(0xacacacacacacacacacacacacacacacac, 128)
);
}
#[test]
fn parse_int_dec() {
assert_eq!(Ok(42), parse_int("42"));
}
#[test]
fn parse_int_hex() {
assert_eq!(Ok(42), parse_int("0x2a"));
}
}