Overview
EasyAND · OR · XOR · shifts · the classic tricks
Numbers are stored as 0s and 1s; flipping and matching those bits lets you do clever tricks fast.
The idea
Bits let you pack flags, toggle state, and do arithmetic without loops. The essentials: & masks, | sets, ^ toggles, and x & (x−1) clears the lowest set bit.
The trick
- x & (x − 1) drops the lowest 1-bit.
- x & -x isolates the lowest 1-bit.
- a ^ a = 0, a ^ 0 = a — the basis of many XOR tricks.
1
1
0
1
0
1
2
3
value13
places8 4 2 1
Step 1 of 7. Computers store every number as bits — just 0s and 1s. Here is 13 written as 1101. Values: 1, 1, 0, 1. value 13, places 8 4 2 1.
1/7
Optimal
timeO(1)spaceO(1)
The moves worth memorizing.
1x & 1 // is odd?2x >> 1 // divide by 23x | (1 << i) // set bit i4x & ~(1 << i) // clear bit i5x ^ (1 << i) // toggle bit i6x & (x - 1) // clear lowest set bitInput
- array
- [1, 1, 0, 1]
Memory
- value
- 13
- places
- 8 4 2 1
- last bit
- —
Output
- odd?
- —
- value
- 13
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- 12 & 10, 12 | 10, 12 ^ 10
- Output:
- 8, 14, 6
- Explanation:
- 1100 and 1010: AND keeps bits set in both, OR keeps either, XOR keeps exactly one. Written in binary the answers are obvious.
Example 2
- Input:
- n = 12; n & (n - 1)
- Output:
- 8
- Explanation:
- Subtracting one flips the lowest set bit and everything under it, so the AND clears it. Repeat and you have counted the set bits.
Finished the walkthrough? Add it to your streak.