🧩 Python DSA Patterns — Bit Manipulation 🧠🐍

Bit manipulation works directly at the binary level — using 0s and 1s to solve problems efficiently. Instead of relying on extra data structures or complex logic, many problems can be reduced to simple bitwise operations that run in constant time.

This pattern is extremely common in problems involving uniqueness, parity, flags, and subset generation.

📝 Check Even or Odd Using Bits

The least significant bit (LSB) determines whether a number is even or odd.

def is_even(n):
    return (n & 1) == 0

print(is_even(4))  # True
print(is_even(7))  # False

💡 Why it works:

Even numbers end in 0 in binary, odd numbers end in 1.

📝 Find the Single Number (XOR Trick)

When every number appears twice except one, XOR cancels duplicates.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    print("Single Number:", result)

single_number([4, 1, 2, 1, 2])

💡 Key insight:

a ^ a = 0 and a ^ 0 = a.

📝 Count Set Bits (Brian Kernighan’s Algorithm)

Efficiently count how many 1s are present in a number’s binary representation.

def count_set_bits(n):
    count = 0
    while n:
        n = n & (n - 1)
        count += 1
    print("Set Bits Count:", count)

count_set_bits(13)  # 1101 → 3

💡 Insight:

Each operation removes the lowest set bit, reducing iterations.

📝 Generate Subsets Using Bit Masking

Every number from 0 to (2ⁿ - 1) represents a unique subset.

def generate_subsets(nums):
    n = len(nums)
    subsets = []

    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        subsets.append(subset)

    print("Subsets:", subsets)

generate_subsets([1, 2, 3])

💡 Why this matters:

This is the foundation for bitmask DP and subset enumeration problems.

🧠 Where Bit Manipulation Is Used

• 🔢 Finding unique or missing numbers
• 🔁 Subset generation & mask-based DP
• 🚦 Flag toggling & state representation
• ⚡ Performance-critical optimizations
• 🧩 Low-level algorithmic tricks

✅ Takeaway

• Bit manipulation provides fast, elegant solutions
• XOR is especially powerful for uniqueness problems
• Shifts (<<, >>) help with masks and powers of two
• Many problems become simpler when viewed in binary

Once comfortable, bit tricks feel like shortcuts hidden in plain sight.

🏋️ Practice Problems

1. Single Number
2. Counting Bits
3. Power of Two
4. Subsets
5. Missing Number

📂 Full Script

The blog covers the essentials — find the complete notebook with all snippets & extras on GitHub Repo 👉 Python DSA Patterns