name: Bit Manipulation
slug: bit-manipulation
difficulty_level: 2
pattern_type: technique
display_order: 19

description: >
  Techniques using binary operations (AND, OR, XOR, NOT, shifts) to solve
  problems efficiently, often achieving O(1) space where other approaches
  need O(n).

when_to_use: |
  - Finding unique elements when pairs cancel out (XOR)
  - Checking powers of 2 (n & (n-1) == 0)
  - Counting set bits (Brian Kernighan's algorithm)
  - Swapping without temp variable (a ^= b; b ^= a; a ^= b)
  - Problems requiring O(1) extra space
  - Toggling or flipping bits

metaphor: |
  Think of XOR like a light switch. Flip it once (XOR with a number) and
  the light turns on. Flip it again with the same number and it turns off.
  Numbers that appear twice "flip twice" and cancel out, leaving only the
  single number.

  Another analogy: imagine each number is a musical note. Playing the same
  note twice creates silence (destructive interference). When you play all
  notes together, pairs cancel out, and only the unique note remains audible.

core_concept: |
  Bit manipulation uses properties of binary operations to solve problems
  elegantly. The most important operations:

  **XOR (⊕):**
  - `a ⊕ a = 0` — any number XORed with itself is zero
  - `a ⊕ 0 = a` — XORing with zero preserves the value
  - XOR is commutative and associative — order doesn't matter

  **AND (&):**
  - `a & (a-1)` removes the lowest set bit
  - `a & 1` checks if a number is odd

  **OR (|):**
  - `a | (1 << k)` sets the k-th bit

  **Shifts:**
  - `a << k` multiplies by 2^k
  - `a >> k` divides by 2^k (floor)

visualization: |
  **XOR Cancellation Example:**

  ```
  nums = [2, 2, 1]

  Step 1: result = 0
          0000 XOR 0010 = 0010 (result = 2)

  Step 2: result = 2
          0010 XOR 0010 = 0000 (pair cancels!)

  Step 3: result = 0
          0000 XOR 0001 = 0001 (result = 1)

  Answer: 1 (the single number)
  ```

  **Bit-by-bit XOR:**

  ```
     0010   (2)
  ⊕  0010   (2)
  --------
     0000   (0) — same bits cancel!

     0000   (0)
  ⊕  0001   (1)
  --------
     0001   (1) — XOR with 0 preserves
  ```

code_template: |
  # XOR all elements - pairs cancel, unique remains
  def find_single(nums: list[int]) -> int:
      result = 0
      for num in nums:
          result ^= num
      return result


  # Check if n is a power of 2
  def is_power_of_two(n: int) -> bool:
      return n > 0 and (n & (n - 1)) == 0


  # Count number of 1 bits (Brian Kernighan)
  def count_bits(n: int) -> int:
      count = 0
      while n:
          n &= (n - 1)  # Remove lowest set bit
          count += 1
      return count


  # Get k-th bit (0-indexed from right)
  def get_bit(n: int, k: int) -> int:
      return (n >> k) & 1


  # Set k-th bit
  def set_bit(n: int, k: int) -> int:
      return n | (1 << k)


  # Clear k-th bit
  def clear_bit(n: int, k: int) -> int:
      return n & ~(1 << k)


  # Toggle k-th bit
  def toggle_bit(n: int, k: int) -> int:
      return n ^ (1 << k)


  # Swap without temp (XOR swap)
  def swap(a: int, b: int) -> tuple[int, int]:
      a ^= b
      b ^= a
      a ^= b
      return a, b


  # Find two single numbers (all others appear twice)
  def find_two_singles(nums: list[int]) -> list[int]:
      # XOR all numbers - result is xor of the two singles
      xor_all = 0
      for num in nums:
          xor_all ^= num

      # Find a bit where the two singles differ
      diff_bit = xor_all & (-xor_all)  # Lowest set bit

      # Partition numbers by this bit and XOR each group
      a, b = 0, 0
      for num in nums:
          if num & diff_bit:
              a ^= num
          else:
              b ^= num

      return [a, b]

recognition_signals:
  - "find the single/unique element"
  - "every element appears twice except one"
  - "O(1) extra space"
  - "XOR"
  - "bit manipulation"
  - "without using extra memory"
  - "power of 2"
  - "count bits"
  - "binary representation"
  - "toggle"
  - "swap without temp"

common_mistakes:
  - title: Forgetting XOR order doesn't matter
    description: |
      XOR is commutative (a⊕b = b⊕a) and associative ((a⊕b)⊕c = a⊕(b⊕c)).
      You can process elements in any order and still get the same result.
    fix: |
      Trust the properties. The order of XOR operations doesn't affect
      the final result. Focus on the logic, not the sequence.

  - title: Using addition instead of XOR
    description: |
      Addition doesn't cancel pairs. 2 + 2 = 4, not 0. XOR is special
      because a ⊕ a = 0 while a + a = 2a.
    fix: |
      Remember: XOR cancels identical values, addition accumulates them.
      Use ^= for pair cancellation, not +=.

  - title: Forgetting to handle negative numbers
    description: |
      XOR works on the binary representation. Negative numbers use two's
      complement, so the bit patterns are different from positive numbers.
    fix: |
      XOR still works correctly with negative numbers in most languages.
      The key properties (a⊕a=0, a⊕0=a) hold for any integer.

  - title: Not recognizing the pattern
    description: |
      Many problems hint at bit manipulation with phrases like "O(1) space"
      or "without extra memory" when dealing with duplicates.
    fix: |
      Look for clues: "appears twice", "unique element", "constant space",
      "power of 2". These often signal bit manipulation approaches.

variations:
  - name: Single Number (pairs cancel)
    description: |
      XOR all elements to find the one that appears once when others
      appear twice.
    example: "Single Number, Single Number II (modular arithmetic)"

  - name: Two Single Numbers
    description: |
      Use XOR to find a differing bit, then partition elements to
      separate the two unique numbers.
    example: "Single Number III"

  - name: Power of Two
    description: |
      Check if n & (n-1) == 0. Powers of 2 have exactly one set bit.
    example: "Power of Two, Power of Four"

  - name: Bit Counting
    description: |
      Count set bits using n &= (n-1) to remove lowest bit each iteration.
    example: "Number of 1 Bits, Counting Bits"

  - name: Bit Masking
    description: |
      Use masks to extract, set, clear, or toggle specific bits.
    example: "Reverse Bits, Bitwise AND of Numbers Range"

related_patterns:
  - greedy
  - dynamic-programming

prerequisite_patterns: []
