Coding Patterns
Bit Manipulation

Bit Manipulation

Bit manipulation involves directly working with individual bits within binary representations of numbers. It is a fundamental technique that allows for highly efficient data processing, enabling constant-time

O(1)
operations for tasks that might otherwise require loops or complex data structures.

At its heart, bit manipulation exploits the binary nature of computers. Every integer is stored as a sequence of 0s and 1s. By operating on these bits directly, you can perform arithmetic and logical operations at the hardware level.

Real-World Analogy

Imagine a large control panel with a row of 32 light switches.

  • 0 represents a switch that is OFF.
  • 1 represents a switch that is ON.
  • An Integer is simply a specific configuration of these 32 switches.

Operations:

  • AND (&): You have two panels superimposed. A light stays ON only if the switch is ON in both panels.
  • OR (|): A light stays ON if the switch is ON in either panel.
  • XOR (^): A light is ON only if the switches are different (one ON, one OFF). If both are ON or both OFF, the light turns OFF.
  • Shift (<<, >>): You slide the entire row of switches left or right.

Visual Explanation

The following diagram visualizes basic bitwise operations on two 4-bit numbers: A = 1010 (Decimal 10) and B = 1100 (Decimal 12).

  graph TD
    subgraph Input
    A["A: 1010 (10)"]
    B["B: 1100 (12)"]
    end

    subgraph Operations
    AND["AND (&): 1000"]
    OR["OR (|): 1110"]
    XOR["XOR (^): 0110"]
    end

    A --> AND
    B --> AND
    A --> OR
    B --> OR
    A --> XOR
    B --> XOR

    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333
    style AND fill:#dfd,stroke:#333
    style OR fill:#dfd,stroke:#333
    style XOR fill:#dfd,stroke:#333

When to Use This Pattern

Use Bit Manipulation when you encounter problems with the following characteristics:

  • Binary Representations: The problem explicitly asks about binary strings, counting bits, or powers of 2.
  • Optimization: You need to optimize space complexity to
    O(1)
    or time complexity from
    O(N)
    to
    O(1)
    or
    O(log N)
    .
  • Sets and States: The problem involves passing around a set of boolean flags or small states (e.g., visited nodes in a small graph).
  • Missing/Duplicates: finding unique or missing elements in an array where other elements repeat (XOR property).
  • Arithmetic Restrictions: You are asked to perform addition, subtraction, or multiplication without using standard operators.

Complexity Analysis

OperationTime ComplexitySpace ComplexityExplanation
Basic Ops (&, |, ^, ~, «, »)
O(1)
O(1)
CPU executes these in a single cycle.
Count Bits
O(log N)
O(1)
Depends on the number of bits (e.g., 32 or 64).
Iterate Subsets
O(2^N)
O(1)
*		Using a mask to generate all subsets of size N.

* Note: Space is O(1) for the iterator, but storing results would be O(2^N).

Common Mistakes

  • Operator Precedence: Bitwise operators often have lower precedence than comparison operators. Always wrap bitwise operations in parentheses. Example: (x & 1) == 0.
  • Signed vs Unsigned Shift: In languages like Java or JavaScript, >> preserves the sign bit (arithmetic shift), while >>> fills with zeros (logical shift). Python handles integers arbitrarily large, so shifts needs care with negative numbers.
  • Integer Overflow: Left shifting 1 << 31 can overflow a signed 32-bit integer, resulting in a negative number or undefined behavior in C++.
  • Infinite Loops: When right-shifting a negative number with >>, it might never reach 0 because 1...1 shifted right is still 1...1 (sign extension).

Next Steps

Now that you understand the core concepts, it’s time to learn the standard code templates and apply them to real problems.

  • Code Templates: Learn the standard “Bitwise Toolbelt” and other reusable patterns.
  • Practice Problems: Solve curated LeetCode problems to master this pattern.