Algorithms / Bitwise Logic
Least You Need to Know: AND, OR, XOR, and Single-Bit Updates
Bitwise operators treat integers as compact boolean vectors. Interview problems use this to test parity, flip flags, cancel duplicates with XOR, and update one bit at a time in constant space.
The least you need to know
- AND keeps only bits that are 1 in both operands.
- OR sets a bit when either operand has a 1 there.
- XOR keeps bits that differ and cancels equal bits.
- Masking isolates or updates one bit without touching others.
- Bitwise reasoning is about per-bit truth tables, not decimal arithmetic intuition.
Key notation
x & mask
keep only masked bits
x | mask
set masked bits to 1
x ^ mask
toggle masked bits
Tiny worked example
- To force bit `k` on, OR with `1 << k`.
- To force bit `k` off, AND with the inverse of `1 << k`.
- To flip bit `k`, XOR with `1 << k`.
- XOR also makes duplicate equal values cancel in pairing problems.
Common mistakes
- Students often use XOR when they meant OR to set a bit permanently.
- Students often forget that XOR cancels only when the same value appears an even number of times.
- Students often reason in decimal instead of comparing individual bit positions.
How to recognize this kind of problem
- The prompt mentions odd/even, flags, masks, duplicates appearing twice, or constant-space state.
- Each feature can be represented as on/off.
- A truth-table view is simpler than a loop over all boolean fields.
Next recommended lesson
Continue through this topic with Least You Need to Know: Boolean Algebra and Bit Reasoning.
Least You Need to Know: Boolean Algebra and Bit ReasoningRelated lessons
Keep going with nearby lessons in the same topic.