Solution to "Single Number II" Leetcode problem

lib.rs

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        let compressed = nums.iter()
            .map(|&n| evenly_space_bits(n as u32))
            .fold(0, |acc, n| omit_threes(acc + n));
        unspace_bits(compressed) as _
    }
}

fn evenly_space_bits(n: u32) -> u64 {
    let n = u64::from(n);
    // 0000 0000 0000 0000  0000 0000 0000 0000  XXXX XXXX XXXX XXXX  XXXX XXXX XXXX XXXX
    // v
    // 0000 0000 0000 0000  XXXX XXXX XXXX XXXX  0000 0000 0000 0000  XXXX XXXX XXXX XXXX
    // v
    // 0000 0000 XXXX XXXX  0000 0000 XXXX XXXX  0000 0000 XXXX XXXX  0000 0000 XXXX XXXX
    // v
    // 0000 XXXX 0000 XXXX  0000 XXXX 0000 XXXX  0000 XXXX 0000 XXXX  0000 XXXX 0000 XXXX
    // v
    // 00XX 00XX 00XX 00XX  00XX 00XX 00XX 00XX  00XX 00XX 00XX 00XX  00XX 00XX 00XX 00XX
    // v
    // 0X0X 0X0X 0X0X 0X0X  0X0X 0X0X 0X0X 0X0X  0X0X 0X0X 0X0X 0X0X  0X0X 0X0X 0X0X 0X0X
    //
    // 0xF = 0b1111
    // 0xC = 0b1100, 0x3 = 0b0011
    // 0x2 = 0b0010, 0x1 = 0b0001

    let n = ((n & 0x0000_0000_FFFF_0000) << (1 << 4)) | (n & 0x0000_0000_0000_FFFF);
    let n = ((n & 0x0000_FF00_0000_FF00) << (1 << 3)) | (n & 0x0000_00FF_0000_00FF);
    let n = ((n & 0x00F0_00F0_00F0_00F0) << (1 << 2)) | (n & 0x000F_000F_000F_000F);
    let n = ((n & 0x0C0C_0C0C_0C0C_0C0C) << (1 << 1)) | (n & 0x0303_0303_0303_0303);
    let n = ((n & 0x2222_2222_2222_2222) << (1 << 0)) | (n & 0x1111_1111_1111_1111);
    n
}

fn unspace_bits(n: u64) -> u32 {
    let n = ((n & 0x4444_4444_4444_4444) >> (1 << 0)) | (n & 0x1111_1111_1111_1111);
    let n = ((n & 0x3030_3030_3030_3030) >> (1 << 1)) | (n & 0x0303_0303_0303_0303);
    let n = ((n & 0x0F00_0F00_0F00_0F00) >> (1 << 2)) | (n & 0x000F_000F_000F_000F);
    let n = ((n & 0x00FF_0000_00FF_0000) >> (1 << 3)) | (n & 0x0000_00FF_0000_00FF);
    let n = ((n & 0x0000_FFFF_0000_0000) >> (1 << 4)) | (n & 0x0000_0000_0000_FFFF);
    n as _
}

fn omit_threes(n: u64) -> u64 {
    const ODD_BITS: u64 = 0x5555_5555_5555_5555;
    const EVEN_BITS: u64 = ODD_BITS << 1;

    let has_threes = ((n & EVEN_BITS) >> 1) & (n & ODD_BITS);
    let allow_nonthrees = (!has_threes) & ODD_BITS;
    let nonthrees_mask = allow_nonthrees | (allow_nonthrees << 1);
    n & nonthrees_mask
}