Bit Manipulation Patterns

What you'll learn

• The Golden Rule

  Use bit manipulation when: - XOR for finding unique/missing elements among pairs - Bitmask for representing subsets or compressed state - Bit tricks for O(1) arithmetic operations (power-of-two check, counting bits) Key XOR properties th…

• Pattern 1: Find the Single Non-Repeating Number

  Problem: Every element appears twice except one. Find the unique element.

• Why XOR Works

  XOR all elements together. Pairs cancel (a ^ a = 0), leaving only the unpaired element. Time: O(n), Space: O(1). No sorting, no hash map needed. ---

• Pattern 2: Find Two Non-Repeating Numbers

  Problem: Every element appears twice except two unique elements. Find both.

• Strategy

  1. XOR all elements → get xorresult = a ^ b (the XOR of the two unique numbers) 2. Find any set bit in xorresult (this bit differs between a and b) 3. Partition all elements into two groups based on that bit 4. XOR each group separately…

• Why This Works

  ---

• Pattern 3: Find Missing Number (XOR Approach)

  Problem: Array of n distinct numbers from range [0, n]. One is missing. XOR all array elements with all numbers 0 to n. Pairs cancel, leaving the missing number. ---

• Pattern 4: Count Set Bits (Brian Kernighan's Algorithm)

  Problem: Count the number of 1-bits in an integer.

• The Trick: n & (n - 1) Removes the Rightmost Set Bit

  Count how many times you can do this before n becomes 0. Time: O(k) where k = number of set bits (not O(32) for all bits). ---

• Pattern 5: Power of Two Check

  Problem: Determine if a number is a power of 2.

• Insight

  Powers of 2 have exactly one set bit: 1, 10, 100, 1000, ... Using the previous trick: if n & (n-1) == 0, there is only one set bit → power of 2. ---

• Pattern 6: Subset Generation with Bitmask

  Problem: Generate all subsets of a set with n elements.

• The Bitmask Approach

  For n elements, iterate from 0 to 2^n - 1. Each number's binary representation indicates which elements to include. ---

• Pattern 7: Bitmask Dynamic Programming

• Concept

  Use a bitmask to represent which items have been "used" or "visited." This compresses exponential state into an integer.

• Example: Minimum Cost to Visit All Nodes

  Time: O(2^n n^2), Space: O(2^n n) ---

• Pattern 8: Reverse Bits

  Problem: Reverse the bit pattern of a 32-bit integer. Each iteration: extract the last bit of n, append it to result, shift n right. ---

• Pattern 9: Number Complement (Flip Bits)

  Problem: Flip all bits of a positive integer (within its significant bits).

• Strategy

  Find a mask with all 1s up to the highest set bit, then XOR. Why XOR with all-ones flips: 1 ^ 1 = 0 and 0 ^ 1 = 1. ---

• Quick Reference: Essential Bit Operations

  | Operation | Expression | Purpose | |-----------|-----------|---------| | Check if bit i is set | n & (1 0 and n & (n-1) == 0 | Exactly one set bit? | | All 1s mask (k bits) | (1 << k) - 1 | Create bitmask | ---

• Complexity Summary

  | Pattern | Time | Space | |---------|------|-------| | Single number (XOR) | O(n) | O(1) | | Two singles | O(n) | O(1) | | Missing number | O(n) | O(1) | | Count set bits | O(k) k=set bits | O(1) | | Power of 2 | O(1) | O(1) | | All sub…

• Pattern Recognition Checklist

  Ask yourself: 1. Are elements paired/duplicated with one or two unique? → XOR 2. Do I need to represent subsets of n items? → Bitmask 3. Can I replace hash sets of small integers with a single integer? → Bitmask DP 4. Is there an O(1) bi…