Bit Manipulation
Use bitwise operators to perform computations directly on binary representations — often O(1) solutions to seemingly hard problems.
Core Concepts
Bitwise tricks let you solve problems that would otherwise require O(n) operations in O(1). Master these fundamental operations:
- AND (&): Both bits must be 1. Used to mask/check specific bits.
- OR (|): At least one bit is 1. Used to set specific bits.
- XOR (^): Bits differ. XOR of a number with itself = 0. Used to find unique elements.
- Left Shift (<<): Multiply by powers of 2.
- Right Shift (>>): Divide by powers of 2.
- NOT (~): Flip all bits.
Cheatsheet Formulas
- Check if n is even:
(n & 1) == 0 - Check if power of 2:
n > 0 && (n & (n-1)) == 0 - Clear lowest set bit:
n & (n - 1)— use to count set bits (Brian Kernighan) - Get lowest set bit:
n & (-n) - XOR trick — find unique: XOR all elements → duplicate pairs cancel to 0
- Swap without temp:
a ^= b; b ^= a; a ^= b; - Count set bits: Loop
n &= (n-1)until n = 0; count iterations