Lesson 194
Bit Manipulation
Operators · Masks · Tricks
1:00How to read and rewrite individual bits directly using AND, OR, XOR, NOT, and shifts — plus the classic tricks that show up across systems and interviews.
By the end, you can
- Apply AND, OR, XOR, NOT, and shifts to compute results bit-by-bit and predict the output.
- Explain why `&` and `&&` behave differently, and why arithmetic right shift on negatives is not plain division.
- Build masks to check, set, clear, or toggle any single bit at position k.
- Use `n & 1`, `n & -n`, and `n & (n-1)` as ready-made idioms.
- Test whether a positive integer is a power of two and explain why the `n > 0` guard is required.
- Trace Kernighan's algorithm to count set bits in O(set bits) time.
- Exploit XOR's self-cancellation to find the lone element in a list in O(n) time with O(1) space.
- Identify the three common pitfalls: missing power-of-two guard, sign-extension in right shifts, and confusing `&` with `&&`.
Up next in Coding Interview Patterns
