Bit Manipulation: The Complete Guide

March 2026 · 20 min read

Most programmers think in decimal. Computers think in binary. The gap between these two worlds is where bit manipulation lives. Understanding how to work with individual bits gives you an entire toolkit of tricks that are faster, more memory-efficient, and often more elegant than their arithmetic equivalents.

This is not an obscure systems programming skill. Bit manipulation shows up everywhere: competitive programming, system design interviews, graphics programming, cryptography, networking, compression algorithms, and embedded systems. It is also one of the most commonly tested topics in coding interviews at companies like Google, Meta, and Amazon.

Why Bits Matter

Every value your program works with is, at the hardware level, a sequence of 0s and 1s. When you write int x = 42;, the CPU stores the bit pattern 00000000 00000000 00000000 00101010 in a 32-bit register. Bitwise operators let you manipulate these bits directly, bypassing the abstraction of decimal arithmetic.

Why would you want to?

• Speed: Bitwise operations are the fastest operations a CPU can perform. A single AND, OR, XOR, or shift completes in one clock cycle. Replacing multiplication, division, or modulo with bit shifts can yield measurable speedups in hot loops.
• Space: A single 32-bit integer can store 32 independent boolean flags. That is 32 booleans in 4 bytes instead of 32 bytes. For problems involving subsets, this compression is transformative.
• Elegance: Bit manipulation often yields solutions that feel almost magical. Swapping two variables without a temporary, checking if a number is a power of two in a single expression, or finding a unique element in an array in O(n) time with O(1) space using XOR.

What This Series Covers

This is not a surface-level overview. The goal is to make you fluent enough for competitive programming and for bit-heavy interviews at companies like Google, Anthropic, Meta, and Amazon. The current posts cover the core path; the roadmap below shows the full expansion path from fundamentals to advanced CP techniques.

Module 1: Foundations and representation

1. Number System and Base Conversion: decimal, binary, octal, hexadecimal, positional notation, arbitrary base conversion, and binary/hex grouping.
2. Binary Representation of Integers: unsigned values, fixed-width types, two's complement, sign extension, overflow, and printing bit patterns.
3. Bit Width, Indexing, and C++ Safety: MSB/LSB, 0-indexed bit positions, 1 << k vs 1LL << k, unsigned arithmetic, shift undefined behavior, and C++20 <bit> helpers.

Module 2: Core bitwise operations

4. Bitwise Operators: AND, OR, XOR, NOT, left shift, right shift, truth tables, precedence, and compound assignments.
5. Bit Manipulation Identities: x & -x, x & (x - 1), x | (x - 1), x ^ (x - 1), ~x = -x - 1, carry intuition, and De Morgan's laws.
6. Bit Masks as Sets: membership, insert, erase, union, intersection, difference, complement, bit fields, flags, permissions, and subset representation.
7. Bit Shifting Deep Dive: logical vs arithmetic shifts, multiplication/division by powers of two, negative-number rounding, safe shifts, and overflow hazards.
8. Essential Single-Bit Tricks: set, clear, toggle, check, isolate, and clear bits; parity checks; branchless sign/opposite-sign tricks.

Module 3: Counting, powers, and low-level techniques

9. Counting Bits: naive popcount, Brian Kernighan's algorithm, lookup tables, SWAR, compiler intrinsics, and Hamming distance.
10. Powers of Two and Alignment: power checks, round up/down, highest set bit, floor(log2 n), alignment masks, and modulo by powers of two.
11. Bit Reversal, Rotation, and Byte/Nibble Tricks: reverse bits, rotate left/right, swap adjacent bits/pairs/nibbles, and endianness basics.
12. Bitwise Arithmetic: add without +, subtract via two's complement, multiply/divide with shifts, average without overflow, and overflow-safe reasoning.

Module 4: XOR mastery

13. XOR Fundamentals and Classic Patterns: self-cancellation, parity, single number, missing number, two unique values, XOR prefixes, and range XOR.
14. Gray Code: binary-to-Gray, Gray-to-binary, n-bit generation, hypercube intuition, and interview applications.
15. Binary Trie for XOR Problems: maximum XOR pair, constrained maximum XOR, count pairs with XOR less than K, deletion, and persistent tries.
16. XOR Linear Basis: vector spaces over GF(2), maximum subset XOR, rank, representability, minimum XOR, and k-th XOR value.

Module 5: Subsets and state compression

17. Subset Enumeration Patterns: all masks, submasks, supersets, split masks, masks by popcount, and why nested submask loops are O(3^n).
18. Bitmask Dynamic Programming Basics: state compression, TSP, assignment DP, Hamiltonian paths, and memoization vs tabulation.
19. Advanced Bitmask DP: profile DP, broken-profile tiling, connected-subset DP, meet-in-the-middle with masks, pruning, and memory optimization.
20. SOS DP and Zeta/Mobius Transforms: sum over subsets, sum over supersets, subset zeta transform, Mobius inversion, OR transform, and AND transform.
21. Fast Walsh-Hadamard Transform: XOR convolution, OR convolution, AND convolution, and when transform-based bit DP beats quadratic approaches.
22. Bitset Optimization: std::bitset, dynamic bitsets, bitset knapsack, transitive closure, string matching speedups, and graph reachability.

Module 6: Range queries, data structures, and greedy construction

23. Range Bitwise Queries: prefix XOR, range AND/OR properties, bit-count prefix arrays, and segment trees for OR/AND/XOR.
24. Bitwise Greedy: build answers from MSB to LSB, maximize/minimize XOR, maximize AND/OR under constraints, and constructive bit problems.
25. Binary Tries Beyond XOR: minimum XOR pair, range maximum XOR, count constrained pairs, deletion, frequency counters, and persistent versions.
26. Binary Digit DP: count values by popcount, count pairs by XOR/AND constraints, tight flags over binary bounds, and digit DP plus bitmask state.
27. Bitwise Graph and Search Problems: BFS over masks, shortest path with visited-state masks, Steiner tree DP, key/lock grids, dominance, and pruning.

Module 7: CP and interview mastery

28. Nim, Sprague-Grundy, and XOR Invariants: nim-sum, winning states, Grundy numbers, and game-theory XOR reasoning.
29. Bitwise Hashing and Randomization: XOR hashing, Zobrist hashing, SplitMix64-style mixing, collision intuition, and CP pitfalls.
30. Google/Anthropic Interview Bit Patterns: reverse bits, sum without plus, UTF-8 validation, range AND, single-number variants, maximum XOR, subnet masks, and permissions.
31. Competitive Programming Bit Pattern Catalog: how to recognize XOR, subset DP, binary trie, bitset optimization, greedy-by-bit, and transform problems from constraints.
32. Capstone: Mixed Bit Manipulation Problems: a curated easy-to-expert ladder with pattern recognition, multiple solutions, edge cases, and a final cheat sheet.

Prerequisites

You need only a basic understanding of C++ (or any C-family language). No prior knowledge of binary or bitwise operations is assumed. We build everything from first principles.

Notation Used in This Series

Throughout this series we use the following conventions:

• 0b prefix for binary literals: 0b1010 = 10 in decimal
• 0x prefix for hexadecimal: 0xFF = 255
• Bit positions are numbered right to left, starting at 0. In 0b1010, bit 1 is set (value 2) and bit 3 is set (value 8).
• When showing 32-bit patterns, we group them in 8-bit chunks: 00000000 00000000 00000000 00101010

Quick Reference Cheat Sheet

Keep this table handy as you work through the series. Every operation is explained in detail in its dedicated post.

Let's Begin

Start with Number System to build a rock-solid foundation in binary, octal, hexadecimal, and base conversion before moving into integer representation details.

Practice Problems

A sampler spanning the whole series, ordered roughly easy → hard. Tags hint at what each problem drills. Work through these as you finish the corresponding posts.

• LeetCode 191 — Number of 1 Bits popcount warm-up for counting set bits; covered in Part 6.
• LeetCode 136 — Single Number XOR the canonical XOR-cancels-pairs problem; Part 8.
• LeetCode 268 — Missing Number XOR XOR all indices with all values; Part 8.
• LeetCode 338 — Counting Bits DP · popcount classic dp[i] = dp[i >> 1] + (i & 1); Part 6.
• LeetCode 78 — Subsets bitmask enumeration iterate all $2^n$ masks; Part 10 prerequisite.
• LeetCode 421 — Maximum XOR of Two Numbers trie · greedy bits bit-by-bit MSB-first; Part 8.
• CSES — Bit Strings powers of two compute $2^n \bmod 10^9{+}7$ via fast exponentiation; Part 7.
• LeetCode 698 — Partition to K Equal Sum Subsets bitmask DP classic subset-state DP; Part 10.
• LeetCode 1125 — Smallest Sufficient Team bitmask DP · set cover states are skill bitmasks; Part 10.
• LeetCode 1986 — Minimum Number of Work Sessions bitmask DP subset enumeration with feasibility; Part 10.