Documentation Index
Fetch the complete documentation index at: https://swe.aboneda.com/llms.txt
Use this file to discover all available pages before exploring further.
Bit Manipulation
Understanding how numbers are represented in binary and leveraging bitwise operations for efficient problem solving.Core Bitwise Operators
| Operator | Symbol | Description |
|---|---|---|
| AND | & | Both bits must be 1 |
| OR | | | At least one bit must be 1 |
| XOR | ^ | Bits must differ |
| NOT | ~ | Flip all bits |
| Left Shift | << | Shift bits left (multiply by 2) |
| Right Shift | >> | Shift bits right (divide by 2) |
Common Tricks
- Check if number is even/odd:
n & 1(0 = even, 1 = odd) - Check if power of 2:
n & (n - 1) == 0 - Toggle a bit at position i:
n ^ (1 << i) - Set a bit at position i:
n | (1 << i) - Clear a bit at position i:
n & ~(1 << i) - Get lowest set bit:
n & (-n) - Clear lowest set bit:
n & (n - 1)
XOR Properties
a ^ a = 0(self-cancellation)a ^ 0 = a(identity)- XOR is commutative and associative
Classic Problems
- Single Number (find the unique element)
- Counting Bits
- Reverse Bits
- Hamming Distance
- Subsets generation using bitmask
- Missing Number (
XOR 0..nwith array)
When to Use
- Problems involving toggling, swapping, or checking individual bits
- Subset enumeration (bitmask DP)
- Finding unique/missing elements efficiently
- Optimizing space when storing boolean flags