Bit Manipulation¶
Also known as: Bitwise Tricks, XOR Tricks
Work on the binary representation directly. The single idea worth its weight: XOR-ing a number with itself gives zero, so XOR-ing an entire array where everything appears twice except one thing leaves exactly that thing behind.
Before you start¶
- Comfortable with binary representation and basic arithmetic in your language.
What 'solved properly' looks like
Target: O(n) time, O(1) space. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You use bitwise operators — AND, OR, XOR, NOT, shifts — directly on the binary representation of numbers. The most powerful trick is XOR: a ^ a = 0, a ^ 0 = a, and XOR is commutative and associative. This means XOR-ing every element in an array where all but one appear twice leaves the unique element as the result, without any extra space.
Why it matters: Bit manipulation appears in exactly one type of interview question — the kind where the constraints "O(1) space" and "O(n) time" with a non-obvious XOR solution are the entire challenge. It's a small pattern but a high-signal one: missing it when it's the intended solution looks bad, but reaching for it when a hash set would do is worse.
When to reach for it¶
Reach for it when a problem says "appears once" when everything else appears twice, "counting set bits", "powers of two", "without using arithmetic operators", or when subsets can be encoded as a bitmask.
When not to use it
Integer width and sign behaviour differ by language — negative numbers and the distinction between arithmetic and logical right-shift will bite you, and this is one of the few places where the language genuinely matters. Bit tricks also destroy readability, so use them only when the problem is about bits, not to show off.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Number of 1 Bits | LeetCode | Easy | 10 mins | teaching |
| 2 | Single Number | LeetCode | Easy | 15 mins | teaching |
| 3 | Counting Bits | LeetCode | Easy | 15 mins | consolidation |
| 4 | Reverse Bits | LeetCode | Easy | 15 mins | consolidation |
| 5 | Sum of Two Integers | LeetCode | Medium | 25 mins | challenge |
Already know this? Test out.
If you can solve Sum of Two Integers cleanly in one sitting — handling the carry logic without using the + operator — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.