Back to DSA DashboardConcept Mastery
DSA Core Concept
Bit Manipulation
Bit Manipulation is the process of applying bitwise operations (AND, OR, XOR, NOT, shifts) directly on binary numbers at the bit level.
Why It Exists
Under the hood, computers store data as binary bits. Bitwise operations execute directly on CPU registers, bypassing standard mathematical units for speed.
Intuition for Beginners
“Think of light switches. Each switch represents 1 (on) or 0 (off). Bitwise operations let you flip, mask, or read configurations of multiple switches in a single clock cycle.”
Visual Explanation
Bitwise XOR (A ^ B) logic: A: 0 1 0 1 (5) B: 0 0 1 1 (3) -------------- XOR: 0 1 1 0 (6) (Different bits yield 1, same bits yield 0)
Complexity Analysis
| Operator | Meaning | CPU Cycles | Notes | |
|---|---|---|---|---|
| & (AND) | Yields 1 if both are 1 | 1 cycle | Used to mask bits | |
| **\ | (OR)** | Yields 1 if any is 1 | 1 cycle | Used to set bits |
| ^ (XOR) | Yields 1 if bits differ | 1 cycle | XOR with self is 0 | |
| << / >> | Shift bits left/right | 1 cycle | Multiply/divide by 2 |
Production & Real World Applications
- •Cryptographic Hashes: Scrambling data states using XOR registers.
- •Graphics Buffers: Combining color pixels via bit masks.
Algorithmic Patterns
XOR Cancellation
Leveraging A ^ A = 0 and A ^ 0 = A properties to cancel duplicate numbers.
Bit Masking
Using `1 << i` to check, set, or clear the ith bit of a number.
Defending the Design (Interview Q&A)
Q:How do you check if a number is a power of two in constant time?
A power of two in binary has exactly one bit set to 1 (e.g. 8 is 1000). Subtracting 1 flips all bits (7 is 0111). Doing `(n & (n - 1)) === 0` will yield 0 if the number is a power of two.
Common Traps & Mistakes
- ⚠️Confusing logical operators (&&, ||) with bitwise operators (&, |).
- ⚠️Off-by-one errors when shifting bits beyond bit limits.