Bit Manipulation
The problem
Some problems (set membership over a small universe, toggling flags, extremely tight memory or performance budgets) are solved dramatically faster or more compactly by operating directly on a number's individual bits than by using higher-level data structures built on top of them.
Why now
Number systems and bases already established binary representation, but treated the individual bits as an implementation detail hidden underneath ordinary arithmetic. Bit manipulation is where those bits become directly manipulable data — AND, OR, XOR, and shifts operate on them explicitly, which is a different, lower-level skill than just knowing binary exists.
Mental model
Every integer is already a compact array of bits; bitwise operators let you read, set, clear, or toggle any one of them directly, in O(1), without touching the rest — a bitmask is a whole set of true/false flags packed into one number, which is why bit manipulation often replaces an array of booleans with a single integer, at a fraction of the memory.
Requires
- Number Systems & BasesMathematical Thinking
Bit manipulation operates directly on the binary representation number-systems-and-bases already introduced; you need positional binary understanding in place before bitwise operators' effects are predictable rather than mysterious.
Used in
- Bitmasks representing small sets or flag combinations compactly (permission flags, feature flags)
- XOR-based tricks (finding a single non-duplicate in an array, swapping without a temp variable)
- Low-level performance-critical code (graphics, embedded systems, competitive programming)
- Hash function design and bit-level data compression
Projects
- Use a single integer as a bitmask to represent and manipulate a set of up to 32 boolean flags, implementing set, clear, toggle, and check operations
- Solve the 'find the single number that appears once while all others appear twice' problem using XOR in O(n) time and O(1) space
Examples
- n & (n - 1) clears the lowest set bit — a one-line trick used to count set bits or check if a number is a power of two
- XOR-ing every element in an array where all but one value appears exactly twice leaves only the unpaired value, because x XOR x is always 0
Resources
Mastery checklist
- I can use AND, OR, XOR, and shifts to set, clear, toggle, and check individual bits
- I can implement a bitmask representing a set of flags in a single integer
- I can explain and apply the XOR trick for finding an unpaired element
- I can identify when a bit-manipulation approach would meaningfully outperform a higher-level data structure