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.
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
Worked example
- To force bit
kon, OR with1 << k. - To force bit
koff, AND with the inverse of1 << k. - To flip bit
k, XOR with1 << 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 it
- 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.