A greedy algorithm builds a solution by always taking the choice that looks best right now, never reconsidering. It is fast and simple — but only correct when local choices provably lead to a global optimum. Bit manipulation, meanwhile, uses binary operators (AND, OR, XOR, shifts) for fast, space-free tricks.
Greedy works only sometimes
Greedy is correct when the problem has the greedy-choice property and optimal substructure — activity selection and Huffman coding qualify. The 0/1 knapsack does not, which is why it needs DP.
Two essential bit tricks
isOdd = (n & 1) == 1 // last bit set? double = n << 1 // shift left = x2 lowestClear = x & (x - 1) // turns off the lowest set bit unique = a ^ a // x XOR x = 0 (pairs cancel)
Bit op O(1)→O(1)
Counting set bits via x & (x-1) is O(number of set bits).
⚡ The edge
- Greedy is fast but fragile — only use it when you can argue (or test) that local optimal choices give the global optimum; otherwise reach for DP.
- Key bit facts: n & 1 tests odd/even, n << 1 doubles, and x ^ x = 0 so XOR of a list cancels every value that appears twice.
Worked example
Every number in [4, 1, 2, 1, 2] appears twice except one. Find the single number using XOR.
- XOR all the numbers together. Because x ^ x = 0, every pair cancels out.
- 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0.
- What remains is the unique value, 4 — in O(n) time and O(1) space.
Answer: 4 (XOR cancels every pair)
Worked example
Count the set bits in 13 (binary 1101) using x & (x-1).
- x & (x-1) removes the lowest set bit each time, so count the removals.
- 1101 -> 1100 -> 1000 -> 0000: three removals.
- So 13 has 3 set bits.
Answer: 3 set bits
⚠ Watch out
- Greedy does not always work — the 0/1 knapsack and some coin systems need DP.
- Mind operator precedence: n & 1 == 0 may parse as n & (1 == 0) — use parentheses.
- Right-shifting negative numbers is implementation-dependent; be careful with signed values.