Bit Manipulation

Every integer your program holds is really a row of bits, ones and zeros, each standing for a power of two. Most of the time you never think about that. But a handful of problems crack open beautifully when you operate on those bits directly, often solving in O(1) extra space what a hash map would need O(n) for.

The classic example: an array where every number appears twice except one, and you want the loner. A hash map works, but XOR finds it with a single accumulator and no extra memory, because XOR makes identical values cancel. That kind of trick is what this unit is about, and equally important, when NOT to reach for it.

Bit manipulation is a narrow, sharp tool. It shines on specific structures, pairs that cancel, powers of two, packing a set of yes/no flags into one number, and it is the wrong tool for general counting. This unit teaches the operators, the few tricks worth memorizing, and the recognition that keeps you from forcing bits where a plain hash map belongs.