Bit Operations

Computers store everything as binary (0s and 1s). Bit manipulation operates directly on these bits, enabling fast operations for certain problems. Understanding bitwise operators unlocks efficient solutions for many algorithmic problems.

Binary Representation

Decimal  Binary
0        0000
1        0001
2        0010
3        0011
4        0100
5        0101
6        0110
7        0111
8        1000

// Convert between decimal and binary
format!("{:b}", 10)  // "1010"
usize::from_str_radix("1010", 2).unwrap()  // 10

Bitwise Operators

AND (&)

Both bits must be 1:

  1010  (10)
& 1100  (12)
------
  1000  (8)

print(10 & 12)  # 8

OR (|)

At least one bit is 1:

  1010  (10)
| 1100  (12)
------
  1110  (14)

print(10 | 12)  # 14

XOR (^)

Exactly one bit is 1:

  1010  (10)
^ 1100  (12)
------
  0110  (6)

print(10 ^ 12)  # 6

NOT (~)

Flip all bits:

~ 1010  (10)
------
  0101  (-11 in two's complement)

print(~10)  # -11

Left Shift (<<)

Shift bits left, fill with 0s:

5 << 1 = 10    (101 → 1010)
5 << 2 = 20    (101 → 10100)

print(5 << 1)  # 10
print(5 << 2)  # 20

Right Shift (>>)

Shift bits right:

10 >> 1 = 5    (1010 → 101)
10 >> 2 = 2    (1010 → 10)

print(10 >> 1)  # 5
print(10 >> 2)  # 2

Common Bit Operations

Check if Bit is Set

fn is_bit_set(n: i32, pos: u32) -> bool {
    // Check if bit at position pos is 1 (0-indexed from right)
    (n & (1 << pos)) != 0
}

fn main() {
    println!("{}", is_bit_set(10, 1));  // true  (1010, bit 1 is set)
    println!("{}", is_bit_set(10, 2));  // false (1010, bit 2 is not set)
}

Set a Bit

fn set_bit(n: i32, pos: u32) -> i32 {
    // Set bit at position pos to 1
    n | (1 << pos)
}

fn main() {
    println!("{}", set_bit(10, 0));  // 11 (1010 → 1011)
}

Clear a Bit

fn clear_bit(n: i32, pos: u32) -> i32 {
    // Set bit at position pos to 0
    n & !(1 << pos)
}

fn main() {
    println!("{}", clear_bit(10, 1));  // 8 (1010 → 1000)
}

Toggle a Bit

fn toggle_bit(n: i32, pos: u32) -> i32 {
    // Flip bit at position pos
    n ^ (1 << pos)
}

fn main() {
    println!("{}", toggle_bit(10, 0));  // 11 (1010 → 1011)
    println!("{}", toggle_bit(10, 1));  // 8  (1010 → 1000)
}

Get Rightmost Set Bit

fn rightmost_set_bit(n: i32) -> i32 {
    // Get the rightmost 1 bit
    n & (-n)
}

fn main() {
    println!("{}", rightmost_set_bit(12));  // 4 (1100 → rightmost is 0100)
}

Clear Rightmost Set Bit

fn clear_rightmost_set_bit(n: i32) -> i32 {
    // Clear the rightmost 1 bit
    n & (n - 1)
}

fn main() {
    println!("{}", clear_rightmost_set_bit(12));  // 8 (1100 → 1000)
}

XOR Properties

XOR has special properties useful for algorithms:

a ^ 0 = a         (Identity)
a ^ a = 0         (Self-inverse)
a ^ b ^ a = b     (Cancel out)
a ^ b = b ^ a     (Commutative)
(a ^ b) ^ c = a ^ (b ^ c)  (Associative)

Find Single Number

Find the one number that appears only once (others appear twice):

fn single_number(nums: &[i32]) -> i32 {
    let mut result = 0;
    for &num in nums {
        result ^= num;
    }
    result
}

fn main() {
    println!("{}", single_number(&[2, 3, 2, 4, 3]));  // 4
}

Swap Without Temp Variable

a, b = 5, 7
a = a ^ b
b = a ^ b  # (a ^ b) ^ b = a
a = a ^ b  # (a ^ b) ^ a = b
# Now a = 7, b = 5

Power of Two

A number is a power of 2 if it has exactly one bit set:

fn is_power_of_two(n: i32) -> bool {
    n > 0 && (n & (n - 1)) == 0
}

fn main() {
    println!("{}", is_power_of_two(8));   // true  (1000)
    println!("{}", is_power_of_two(10));  // false (1010)
}

Count Set Bits (Hamming Weight)

fn count_bits(mut n: i32) -> i32 {
    // Count number of 1 bits
    let mut count = 0;
    while n != 0 {
        count += 1;
        n &= n - 1;  // Clear rightmost set bit
    }
    count
}

fn main() {
    println!("{}", count_bits(11));  // 3 (1011 has three 1s)

    // Using built-in method
    println!("{}", 11i32.count_ones());  // 3
}

Hamming Distance

Count positions where bits differ:

def hamming_distance(x, y):
    xor = x ^ y  # Different bits are 1
    return count_bits(xor)

print(hamming_distance(1, 4))  # 2 (0001 vs 0100)

Reverse Bits

def reverse_bits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

print(bin(reverse_bits(0b10100)))  # 0b101 (for 5-bit reversal)

Bitwise Tricks Summary

| Operation | Code | Description | |-----------|------|-------------| | Check bit i | n & (1 << i) | Non-zero if set | | Set bit i | n | (1 << i) | Set to 1 | | Clear bit i | n & ~(1 << i) | Set to 0 | | Toggle bit i | n ^ (1 << i) | Flip | | Clear rightmost 1 | n & (n-1) | Useful for counting | | Get rightmost 1 | n & (-n) | Isolate lowest set bit | | Power of 2? | n & (n-1) == 0 | Single bit set | | n * 2 | n << 1 | Left shift | | n / 2 | n >> 1 | Right shift |

Key Takeaways

1. Bitwise operators work on individual bits: AND, OR, XOR, NOT, shifts
2. XOR is especially useful: a ^ a = 0, a ^ 0 = a
3. n & (n-1) clears rightmost set bit (useful for counting)
4. n & (-n) isolates rightmost set bit
5. Powers of 2 have exactly one bit set
6. Bit operations are O(1) and very fast

Bit manipulation may seem low-level, but it's essential for certain problems and optimizations. The patterns here—checking, setting, clearing bits, and using XOR properties—appear frequently in algorithms.