Bit Manipulation

Bit manipulation uses bitwise operators (&, |, ^, !, <<, >>) and hardware bit intrinsics (count_ones, trailing_zeros, leading_zeros, next_power_of_two) to represent subsets as integer bitmasks, perform branchless arithmetic, and solve XOR parity problems in $O(1)$ register operations.

8-Bit Subset Bitmask: `mask = 0b0010_1100` (Represents the set `{2, 3, 5}`)

  - Check if element `k` is in set:   `(mask & (1 << k)) != 0`
  - Add element `k` to set:           `mask |= 1 << k`
  - Remove element `k` from set:      `mask &= !(1 << k)`
  - Toggle element `k`:               `mask ^= 1 << k`
  - Clear lowest set bit (`2`):       `mask &= mask - 1`  --> `0b0010_1000`
  - Isolate lowest set bit (`1<<2`):  `mask & mask.wrapping_neg()` --> `0b0000_0100`

Note on Bitwise NOT in Rust (! Instead of ~)

Unlike C/C++/Python (which use ~x for bitwise NOT and !x for logical NOT), Rust uses !x for both bitwise NOT on integers (!0u32 == 0xFFFF_FFFF) and logical NOT on booleans (!true == false)!

Built-In Hardware Bit Methods on Rust Integers

Every unsigned integer type (u8, u16, u32, u64, u128, usize) provides portable methods that compile directly to single-cycle CPU instructions:

Iterating Over All Submasks of a Bitmask in $O(3^k)$ Time

In Bitmask Dynamic Programming (where $N \le 20$ elements are represented as a u32 mask), iterating over every non-empty submask sub of a given mask uses the classic bitwise decrement trick sub = (sub - 1) & mask, visiting only valid subsets of mask in $O(3^N)$ total time across all masks (instead of $O(4^N)$!):

/// Returns all non-empty submasks of `mask` in descending order using `sub = (sub - 1) & mask`.
pub fn collect_submasks(mask: u32) -> Vec<u32> {
    let mut submasks = Vec::new();
    let mut sub = mask;
    while sub > 0 {
        submasks.push(sub);
        sub = (sub - 1) & mask;
    }
    submasks
}

/// Finds the single number that appears an odd number of times in `nums` in O(n) time, O(1) space
/// using the XOR self-inverse property (`x ^ x == 0` and `x ^ 0 == x`).
pub fn find_single_number(nums: &[u64]) -> u64 {
    nums.iter().fold(0u64, |acc, &x| acc ^ x)
}

/// Iterates over the set bit indices of `mask` in O(count_ones) steps!
pub fn set_bit_indices(mut mask: u64) -> Vec<u32> {
    let mut indices = Vec::with_capacity(mask.count_ones() as usize);
    while mask != 0 {
        let lowest_bit_idx = mask.trailing_zeros();
        indices.push(lowest_bit_idx);
        mask &= mask - 1; // Clear lowest set bit in 1 instruction
    }
    indices
}

fn main() {
    let mask = 0b1011u32; // Bits 0, 1, and 3 (3 bits -> 2^3 - 1 = 7 non-empty submasks)
    let subs = collect_submasks(mask);
    assert_eq!(subs.len(), 7);

    let unique = find_single_number(&[42, 7, 99, 7, 42]);
    assert_eq!(unique, 99);

    let bits = set_bit_indices(0b1010_0100);
    assert_eq!(bits, vec![2, 5, 7]);

    println!(
        "Submasks of 0b1011: {} items, unique XOR element: {unique}, set bit indices: {bits:?}",
        subs.len()
    );
}

Submasks of 0b1011: 7 items, unique XOR element: 99, set bit indices: [2, 5, 7]