← All patterns
Bit Manipulation
Use bitwise operators (&, |, ^, <<, >>) to solve problems at the bit level, often achieving O(1) space and clever constant-factor speedups.
When to use it
- Problems involving powers of two, even/odd checks, toggling flags.
- 'Find the single number' (XOR cancels duplicates).
- Counting set bits, checking if a number is a power of 2.
Signals in the problem statement
- Keywords: bits, binary, power of two, single number, XOR.
- Space constraint suggests using bits instead of hash sets.
Common pitfalls
- Operator precedence traps: `&` and `|` have lower precedence than `==`, so always use parentheses: `(x & mask) == 0`.
- Signed vs unsigned behavior — right-shift `>>` in JavaScript preserves sign; use `>>>` for logical (zero-fill) shift.
Practice Problems
Single Number
EasyAsked at: Amazon, Google, Apple
Given an array where every element appears twice except for one, find the single one. Use O(1) space.
Time: O(n) · Space: O(1)
Counting Bits
EasyAsked at: Amazon, Meta
Given an integer n, return an array of length n+1 where ans[i] is the number of 1-bits in the binary representation of i.
Time: O(n) · Space: O(n)