Bit Manipulation Patterns

Terminology

Term	Definition
Bitwise AND ($\&$)	Sets each bit to 1 only if both corresponding bits are 1. Used for masking and checking specific bits.
Bitwise OR ($\|$)	Sets each bit to 1 if at least one corresponding bit is 1. Used for setting bits.
Bitwise XOR ($\oplus$)	Sets each bit to 1 if the corresponding bits differ. Key property: $a \oplus a = 0$ and $a \oplus 0 = a$.
Left shift ($\ll$)	Shifts bits left by $k$ positions, equivalent to multiplying by $2^k$. Fills vacated positions with zeros.
Right shift ($\gg$)	Shifts bits right by $k$ positions, equivalent to integer division by $2^k$.
Bitmask	An integer whose binary representation encodes a subset. Bit $i$ is 1 if element $i$ is in the subset. Enables $O(1)$ set operations.
Lowest set bit	The rightmost bit that is 1. Extracted with $n \& (-n)$. Cleared with $n \& (n - 1)$.
Popcount	The number of 1-bits in a binary representation. Also called Hamming weight. Many CPUs have a dedicated instruction for this.

What & Why

Bit manipulation operates directly on the binary representation of integers. It is fast (single CPU instruction per operation), uses no extra memory, and unlocks elegant solutions to problems that seem to require hash maps or sorting.

The most famous trick: XOR all elements in an array where every number appears twice except one. The duplicates cancel out ( $a \oplus a = 0$ ), leaving the unique number. This solves "single number" in $O(n)$ time and $O(1)$ space.

Beyond XOR tricks, bitmasks represent subsets as integers, enabling $O(1)$ membership checks, unions, and intersections. This powers bitmask DP, permission systems, and feature flags.

Bit manipulation is a pattern you either know or you don't. Once you learn the core tricks, a whole class of problems becomes straightforward.

How It Works

XOR Properties

The key properties that make XOR useful:

$a \oplus a = 0$ (self-cancellation)
$a \oplus 0 = a$ (identity)
XOR is commutative and associative: order does not matter

Common Bit Tricks

Check if power of 2: $n \& (n - 1) = 0$ (only one bit is set)
Clear lowest set bit: $n \& (n - 1)$
Isolate lowest set bit: $n \& (-n)$
Count set bits: repeatedly clear the lowest set bit until $n = 0$
Check bit $i$ : $(n \gg i) \& 1$
Set bit $i$ : $n | (1 \ll i)$

Complexity Analysis

Problem	Time	Space
Single number (XOR)	$O(n)$	$O(1)$
Count bits (Brian Kernighan)	$O(k)$ where $k$ = number of set bits	$O(1)$
Power of two check	$O(1)$	$O(1)$
Enumerate all subsets of a bitmask	$O(2^k)$ where $k$ = popcount	$O(1)$

Bitwise operations execute in $O(1)$ on fixed-width integers. For the single number problem, one pass through $n$ elements with one XOR each:

$T(n) = O(n), \quad S = O(1)$

Implementation

Single Number (XOR)

ALGORITHM SingleNumber(A, n)
  INPUT: array A where every element appears twice except one
  OUTPUT: the unique element

  result = 0
  FOR i = 0 TO n - 1 DO
    result = result XOR A[i]
  END FOR
  RETURN result
END

Count Set Bits (Brian Kernighan's Algorithm)

ALGORITHM CountBits(n)
  INPUT: non-negative integer n
  OUTPUT: number of 1-bits in binary representation

  count = 0
  WHILE n > 0 DO
    n = n AND (n - 1)    // clear lowest set bit
    count = count + 1
  END WHILE
  RETURN count
END

Power of Two Check

ALGORITHM IsPowerOfTwo(n)
  INPUT: positive integer n
  OUTPUT: TRUE if n is a power of 2

  RETURN n > 0 AND (n AND (n - 1)) = 0
END

Enumerate All Subsets of a Bitmask

ALGORITHM EnumerateSubsets(mask)
  INPUT: bitmask representing a set
  OUTPUT: all subsets of the set represented by mask

  subsets = empty list
  sub = mask

  REPEAT
    subsets.append(sub)
    sub = (sub - 1) AND mask
  UNTIL sub = mask    // wraps around to mask when sub was 0

  subsets.append(0)   // include empty subset
  RETURN subsets
END

Real-World Applications

Permission systems: Unix file permissions (rwx) and feature flags use bitmasks for $O(1)$ permission checks with bitwise AND.
Network subnet masks: IP address matching uses bitwise AND with subnet masks to determine network membership.
Error detection: CRC checksums and parity bits use XOR operations to detect transmission errors.
Cryptography: XOR is a fundamental building block in stream ciphers, one-time pads, and hash functions.
Graphics programming: alpha blending, color channel extraction, and pixel manipulation all use bitwise operations for performance.

Key Takeaways

XOR's self-cancellation property ($a \oplus a = 0$) solves "find the unique element" in $O(n)$ time and $O(1)$ space
$n \& (n - 1)$ clears the lowest set bit, enabling Brian Kernighan's bit counting and power-of-two checks
Bitmasks represent subsets as integers: bit $i$ set means element $i$ is included. This enables $O(1)$ set operations
Enumerating all subsets of a bitmask uses the trick $\text{sub} = (\text{sub} - 1) \& \text{mask}$, visiting all $2^k$ subsets
Bit manipulation is a constant-factor optimization: it replaces hash maps and arrays with single CPU instructions