DSA & Implementation · core
Bit Manipulation
Bitwise ops, masks, XOR tricks.
Mental model
Bits give you three superpowers: a bitmask is an O(1) set, XOR cancels duplicates, and checking power-of-2 is a single AND. Two tricks worth memorizing: n & (n-1) clears the lowest set bit, and XOR-ing equal values gives zero.
How to study Bit Manipulation
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Bitwise operation (Wikipedia) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Bit Manipulation with the neighboring concepts in its roadmap. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Find the single number (XOR), Single Number, Sum of Two Integers and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Learn from primary sources
Practice and explain it back
Find the single number (XOR)
Every element appears twice except one. Find it in O(n) time, O(1) space.
Expected evidence: xor all → 5 for [4,1,2,1,4].
Open the interactive drill →Single Number
LeetCode #136 — Single Number. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/single-number/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Sum of Two Integers
LeetCode #371 — Sum of Two Integers. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/sum-of-two-integers/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Reverse Bits
LeetCode #190 — Reverse Bits. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/reverse-bits/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Review prompts
- Why does `n & (n - 1)` clear the lowest set bit, and what two things does that give you?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.
Prerequisites
None assigned yet.
Related concepts
None assigned yet.