Chapter 16 — Bit Manipulation
Source:
src/main/kotlin/bitset/Master idea: the bit level is where a few identities do the work of whole data structures: XOR cancels pairs (single-number problems),
n & (n-1)clears the lowest set bit (popcount), a binary trie answers maximum-XOR in O(1) per bit, and shifts encode “multiply by a power of two” (subset-sum formulas).Prerequisites: binary representation, the trie from Chapter 13 (16.5 reuses it with two children), and basic recursion.
Problems at a glance (this chapter’s core set)
| # | Problem | Pattern | Complexity | Page |
|---|---|---|---|---|
| 16.1 | Number Of 1 Bits | n & (n-1) popcount | $O(\text{set bits})$ | → |
| 16.2 | Reverse Bits | bit-by-bit rebuild | $O(32)$ | → |
| 16.3 | Single Number | XOR cancellation | $O(n)$ | → |
| 16.4 | Single Number III | XOR + lowbit split | $O(n)$ | → |
| 16.5 | Maximum XOR Of Two Numbers | binary trie | $O(32n)$ | → |
| 16.6 | Sum Of All Subset XOR Totals | bit-count formula | $O(n)$ | → |
| 16.7 | Smallest Number With All Set Bits | msb → all-ones | $O(\log n)$ | → |
| 16.8 | Pow(x, n) | binary exponentiation | $O(log n)$ | → | | 16.9 | Divide Two Integers | binary long division | $O(log^2)$ | → | | 16.10 | Steps To Reduce Binary Number | carry-aware bit scan | $O(L)$ | → | | 16.13 | Power Of Two | single-bit test | $O(1)$ | → | | 16.14 | Longest Nice Subarray | sliding OR window | $O(n)$ | → |
The rest of the bitset/ directory
src/main/kotlin/bitset/ also holds: First Letter To Appear Twice, Longest Nice Subarray, Number Of Steps To Reduce A Number In Binary Representation To One, and the string/ folder’s binary-string variants. The XOR-family ideas recur in the hash-table/ and string/ folders.
New pages are appended to the table above as they’re written.