Bit Manipulation
Visualize bitwise operations at the binary level.
Operand ADecimal: 12
0
0
0
0
1
1
0
0
AND
Operand BDecimal: 10
0
0
0
0
1
0
1
0
Intuition
Computers store data as bits (0s and 1s). Bit manipulation allows us to operate directly on these bits, which is extremely fast and efficient.
Concept
- AND (&): 1 if both bits are 1.
- OR (|): 1 if at least one bit is 1.
- XOR (^): 1 if bits are different.
- NOT (~): Inverts all bits (0→1, 1→0).
- Left Shift (<<): Shifts bits left, filling with 0. Equivalent to multiplying by 2^k.
- Right Shift (>>): Shifts bits right. Equivalent to dividing by 2^k.
How it Works
Common Tricks:
x & 1: Check if odd (1) or even (0).x & (x - 1): Clear the lowest set bit.x ^ x = 0: XORing a number with itself is 0.x << 1: Multiply by 2.
Step-by-Step Breakdown
Watch the visualization:
- See how each bit column is processed independently (except shifts).
- Observe how shifts move the entire pattern left or right.
When to Use
- Optimizing space (flags, bitmasks).
- Low-level system programming.
- Competitive programming (subset generation, DP optimization).
When NOT to Use
- High-level logic where readability is more important than micro-optimization.
- Floating point arithmetic (unless you know IEEE 754 well).
How to Identify
"Single Number", "Number of 1 bits", "Power of two", "Subsets".
Frequently Asked Questions
What is Bit Manipulation?
Visualize bitwise operations at the binary level.
What is the time complexity of Bit Manipulation?
The time complexity is: Best case varies, Average case O(1), Worst case varies. Space complexity is varies.