Bit Manipulation

Bit manipulation is the practice of using bitwise operators to manipulate individual bits. This technique is extremely fast and memory-efficient, making it crucial for optimization and low-level programming.

Binary Representation

Every number in a computer is stored as a sequence of bits (0s and 1s).

# Decimal 13 in binary
13 = 1101₂ = (1×2³) + (1×2²) + (0×2¹) + (1×2⁰)
   = 8 + 4 + 0 + 1 = 13

Bitwise Operators

Python provides six bitwise operators:

1. AND (&)

Returns 1 only if both bits are 1.

    5 = 0101
  & 3 = 0011
  ----------
    1 = 0001

2. OR (|)

Returns 1 if at least one bit is 1.

    5 = 0101
  | 3 = 0011
  ----------
    7 = 0111

3. XOR (^)

Returns 1 if bits are different.

    5 = 0101
  ^ 3 = 0011
  ----------
    6 = 0110

4. NOT (~)

Flips all bits (inverts).

  ~ 5 = ~0101 = 1010 (in two's complement = -6)

5. Left Shift (<<)

Shifts bits left, multiplies by 2^n.

5 << 1 = 0101 << 1 = 1010 = 10
5 << 2 = 0101 << 2 = 10100 = 20

6. Right Shift (>>)

Shifts bits right, divides by 2^n.

5 >> 1 = 0101 >> 1 = 0010 = 2
5 >> 2 = 0101 >> 2 = 0001 = 1

Common Bit Manipulation Tricks

Check if Number is Even or Odd

def is_even(n):
    return (n & 1) == 0  # Last bit is 0 for even numbers

# Much faster than n % 2 == 0

Check if i-th Bit is Set

def is_bit_set(n, i):
    return (n & (1 << i)) != 0

Set the i-th Bit

def set_bit(n, i):
    return n | (1 << i)

Clear the i-th Bit

def clear_bit(n, i):
    return n & ~(1 << i)

Toggle the i-th Bit

def toggle_bit(n, i):
    return n ^ (1 << i)

Count Set Bits (Population Count)

Count the number of 1s in binary representation.

def count_set_bits(n):
    count = 0
    while n:
        count += n & 1  # Check last bit
        n >>= 1         # Right shift
    return count

# Even faster: Brian Kernighan's Algorithm
def count_set_bits_fast(n):
    count = 0
    while n:
        n &= (n - 1)  # Removes rightmost set bit
        count += 1
    return count

Check if Number is Power of 2

def is_power_of_2(n):
    # Power of 2 has only one bit set
    return n > 0 and (n & (n - 1)) == 0

Why it works:

• 8 = 1000, 8-1 = 0111, AND = 0000
• 7 = 0111, 7-1 = 0110, AND = 0110 (not 0)

Find the Only Non-Duplicate Number

Using XOR property: a ^ a = 0 and a ^ 0 = a

def find_unique(arr):
    result = 0
    for num in arr:
        result ^= num  # XOR cancels duplicates
    return result

# Example: [2, 3, 2, 4, 4] → 3

Swap Two Numbers Without Temp Variable

def swap(a, b):
    a = a ^ b
    b = a ^ b  # b = (a ^ b) ^ b = a
    a = a ^ b  # a = (a ^ b) ^ a = b
    return a, b

Real-World Applications

Permissions (Unix/Linux)

# Permission flags
READ    = 1 << 0  # 001 = 1
WRITE   = 1 << 1  # 010 = 2
EXECUTE = 1 << 2  # 100 = 4

# Grant permissions
permissions = READ | WRITE  # 011 = 3

# Check if has write permission
has_write = (permissions & WRITE) != 0

# Revoke execute permission
permissions &= ~EXECUTE

Network Masks (IP Addresses)

# Subnet mask: 255.255.255.0
# Binary:      11111111.11111111.11111111.00000000

Compression & Cryptography

Bit manipulation is heavily used in compression algorithms (Huffman coding) and encryption (bitwise operations on keys).

Quiz

Key Takeaways

✅ Bitwise operators work directly on binary representations
✅ XOR tricks are powerful for finding unique elements and swapping
✅ n & (n-1) removes rightmost set bit - many applications
✅ Bit manipulation is extremely fast and memory-efficient
✅ Real-world uses in permissions, networking, and cryptography

Master these tricks for competitive programming and optimization! 🚀