Bit Manipulation — Complete Guide

Why Bit Manipulation?

Bitwise operations work directly on binary representations, enabling O(1) tricks that would otherwise need loops or extra space.

Essential Bit Operations

Operation	Expression	Meaning
Check bit i	`(n >> i) & 1`	Is bit i set?
Set bit i	`n` \| `(1 << i)`	Set bit i to 1
Clear bit i	`n & ~(1 << i)`	Set bit i to 0
Toggle bit i	`n ^ (1 << i)`	Flip bit i
Remove last set bit	`n & (n-1)`	Clear rightmost 1
Isolate last set bit	`n & (-n)`	Keep only rightmost 1
Check power of 2	`n > 0 and (n & (n-1)) == 0`
Count set bits	`bin(n).count('1')` or `__builtin_popcount(n)`
XOR self = 0	`n ^ n = 0`	Cancel duplicates
XOR with 0	`n ^ 0 = n`	Identity

The 7 Core Patterns

Pattern 1 — XOR for Duplicate Cancellation

XOR of a number with itself = 0. Use to find single/missing numbers.

# Find single number (all others appear twice)
result = 0
for n in nums: result ^= n

Pattern 2 — Brian Kernighan (Count Set Bits)

n & (n-1) removes the lowest set bit. Count iterations.

count = 0
while n: n &= n-1; count += 1

Pattern 3 — Bitmask DP (Subsets as State)

State = bitmask of items selected. Iterate over all 2^n masks.

for mask in range(1 << n):
    for i in range(n):
        if mask & (1 << i):
            # item i is in this subset

Pattern 4 — Bitmask Enumeration (Subsets of a Mask)

Enumerate all subsets of a bitmask in O(2^popcount) using sub = (sub-1) & mask.

sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask

Pattern 5 — Two's Complement Tricks

Negative numbers in two's complement: -n = ~n + 1. n & (-n) isolates rightmost set bit.

Pattern 6 — Bit by Bit Construction

Build answer bit by bit. Often used with XOR prefix sums.

prefix_xor = 0
for n in nums:
    prefix_xor ^= n
    # query trie for max XOR with prefix_xor

Pattern 7 — Bit Reversal / Rotation

Reverse bits of a 32-bit integer.

result = 0
for _ in range(32):
    result = (result << 1) | (n & 1)
    n >>= 1

Language-specific Bit Operations

Python

n & m   # AND
n | m   # OR
n ^ m   # XOR
~n      # NOT (bitwise complement)
n << k  # left shift
n >> k  # right shift
bin(n).count('1')  # popcount

C/C++

n & m; n | m; n ^ m; ~n; n << k; n >> k;
__builtin_popcount(n);    // GCC popcount
__builtin_clz(n);         // count leading zeros
__builtin_ctz(n);         // count trailing zeros

Java

n & m; n | m; n ^ m; ~n; n << k; n >> k; n >>> k; // unsigned right shift
Integer.bitCount(n);
Integer.highestOneBit(n);
Integer.numberOfLeadingZeros(n);

JavaScript

n & m; n | m; n ^ m; ~n; n << k; n >> k; n >>> k;
// No built-in popcount; use:
n.toString(2).split('').filter(x=>x==='1').length

Problem Index

#	Problem	Pattern	Difficulty
01	Single Number I	XOR cancel	Easy
02	Single Number II	Bit counting 3-state	Medium
03	Single Number III (two singles)	XOR + partition	Medium
04	Number of 1 Bits (Hamming Weight)	Brian Kernighan	Easy
05	Counting Bits	DP with bits	Easy
06	Reverse Bits	Bit-by-bit	Easy
07	Missing Number	XOR or math	Easy
08	Find the Difference	XOR	Easy
09	Power of Two	n & (n-1) == 0	Easy
10	Sum of Two Integers (no +)	Bit addition	Medium
11	Maximum XOR of Two Numbers	Binary Trie	Medium
12	Subsets	Bitmask enumerate	Medium
13	Total Hamming Distance	Bit position analysis	Medium
14	Bitwise AND of Numbers Range	Common prefix	Medium
15	Divide Two Integers	Bit shifting	Medium
16	Minimum XOR Sum (Bitmask DP)	Bitmask DP	Hard
17	Partition to K Equal Sum Subsets	Bitmask DP	Medium
18	Bit Manipulation Master Recap	Cheatsheet	—