DSA: Bit Manipulation

Master bitwise operators, classic bit tricks, subset generation, and XOR applications.

Bitwise Operators and Core Tricks

Six bitwise operators operate on individual bits of integers. Mastering them unlocks O(1) solutions for many problems that would otherwise require loops.

Bitwise Operators

AND, OR, XOR, NOT, left shift, right shift, all operate in O(1) on hardware.

  • AND (&): both bits 1 ā†’ result 1. Use: masking, checking bits
  • OR (|): either bit 1 ā†’ result 1. Use: setting bits
  • XOR (^): bits differ ā†’ result 1. Use: toggling, finding unique elements
  • NOT (~): flip all bits. Use: creating masks
  • Left shift (<<): multiply by 2^k. Right shift (>>): divide by 2^k

Core Bit Operations

C++

Set, clear, toggle, check a specific bit, all in O(1).

Power of 2 and Count Set Bits

Two of the most common bit tricks: checking if a number is a power of 2 in O(1), and counting set bits (popcount) in O(number of set bits) using Brian Kernighan's algorithm.

Power of 2 and Popcount

Power of 2: exactly one bit set, so n & (n-1) clears it to 0. Kernighan: n & (n-1) removes lowest set bit each iteration.

  • isPow2: n > 0 && (n & (n-1)) == 0
  • n & (n-1) clears the lowest set bit of n
  • Kernighan's loop runs exactly popcount(n) times
  • __builtin_popcount(n) is the compiler intrinsic (O(1) hardware instruction)

Power of 2 and Count Set Bits

C++

Kernighan's loop: clears one set bit per iteration, runs in O(popcount).

Find Single Number (XOR)

In an array where every element appears twice except one, XOR all elements. Pairs cancel to 0 (x ^ x = 0) and the lone element remains (x ^ 0 = x).

XOR Properties

x ^ x = 0, x ^ 0 = x, XOR is commutative and associative, order of XOR-ing does not matter.

  • All duplicates XOR to 0; single element XOR 0 = itself
  • Time: O(n), Space: O(1), no hash map needed
  • Extension: find two non-repeating elements using the rightmost set bit of their XOR
  • XOR also used for in-place swap: a^=b; b^=a; a^=b

Find Single / Two Non-Repeating Elements

C++

XOR cancels pairs; rightmost differing bit separates the two unique elements.

Reverse Bits and Swap Odd-Even Bits

Reverse all 32 bits of an integer, and swap all odd-positioned bits with even-positioned bits using masks and shifts.

Bit Reversal and Odd-Even Swap

Reverse: process bit by bit. Odd-even swap: mask even bits (0xAAAA...), mask odd bits (0x5555...), shift and OR.

  • Reverse: shift result left, add LSB of n, shift n right, 32 iterations
  • Odd-even swap: even bits mask = 0x55555555, odd bits mask = 0xAAAAAAAA
  • Swap: ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
  • Both run in O(1) with fixed 32 iterations or constant operations

Reverse Bits and Swap Odd-Even Bits

C++

Fixed masks isolate even/odd bit positions; shifts move them into place.

Generate All Subsets Using Bitmasks

Every integer from 0 to 2^n - 1 encodes a unique subset of an n-element set. Biti set in the mask means elementi is included.

Subset Enumeration

2^n masks cover all subsets. For each mask, iterate bits to collect included elements.

  • Total subsets of n elements = 2^n
  • mask from 0 to (1<
  • Empty set = mask 0; full set = mask (1<
  • Foundation for bitmask DP (TSP, assignment problems)
  • Time: O(2^n * n) to enumerate all subsets

All Subsets via Bitmask

C++

Each integer 0 to 2^n-1 is a subset mask; bit i set = include arr[i].

XOR Applications

XOR has unique self-inverse and cancellation properties that enable elegant O(1) space solutions for several common problems.

XOR Use Cases

XOR is its own inverse: a^b^b = a. No extra space needed for problems that exploit this.

  • In-place swap: a^=b; b^=a; a^=b (no temp variable)
  • Find missing number in [0..n]: XOR all indices with all values
  • Bits to flip A to B: popcount(A ^ B)
  • Detect if two integers have opposite signs: (a ^ b) < 0
  • Add without + operator: sum = a^b (no carry), carry = (a&b)<<1, repeat

XOR Applications

C++

Find missing number and add without + using only XOR and AND.

Bit Masking in DP

Bitmask DP encodes a subset of elements as the DP state, enabling efficient solutions for problems with small n (typically n up to 20). The TSP bitmask DP is the canonical example.

Bitmask DP Pattern

State = (mask, last element). Transition = add one unvisited element. Total states = 2^n * n.

  • mask bit i set = element i has been used/visited
  • Iterate masks in increasing order: smaller masks computed before larger ones
  • Check if bit set: mask & (1<
  • Enumerate unset bits: for each i where !(mask & (1<
  • Used in TSP, assignment problem, covering problems, minimum XOR partition

Bitmask DP: Assignment Problem

C++

mask = set of assigned jobs; popcount(mask) = next worker index.

Bit Tricks Quick Reference

Common one-liners used in competitive programming and interviews.

OperationExpressionWhy it works
Check k-th bitn & (1 << k)Mask isolates bit k
Set k-th bitn | (1 << k)OR forces bit k to 1
Clear k-th bitn & ~(1 << k)AND with complement clears bit k
Toggle k-th bitn ^ (1 << k)XOR flips bit k
Is power of 2n > 0 && !(n & n-1)Powers of 2 have exactly one set bit
Clear lowest set bitn & (n - 1)n-1 flips all bits up to lowest set bit
Isolate lowest set bitn & (-n)Two's complement trick
Count set bits__builtin_popcount(n)Hardware popcount instruction
Bits to flip A to Bpopcount(A ^ B)XOR marks differing bits
Swap a and ba^=b; b^=a; a^=bXOR self-inverse property

Knowledge Check

1. How do you check if the k-th bit (0-indexed) of n is set?

2. A number n is a power of 2 if and only if:

3. Brian Kernighan's algorithm counts set bits by:

4. XOR of a number with itself equals:

5. To find the single non-repeating element when all others appear twice:

6. How many subsets does a set of n elements have, and how are they represented with bits?

7. To clear the k-th bit of n:

8. The number of bits to flip to convert A to B equals:

PreviousNext