Bit Manipulation
Bit Manipulation
Bit manipulation involves working with the individual bits of a number's binary representation. It can lead to extremely fast and memory-efficient solutions for certain types of problems.
Core Bitwise Operators
| Operator | Name | Description |
|---|---|---|
| & | AND | Sets bit to 1 if both bits are 1. |
| | | OR | Sets bit to 1 if at least one bit is 1. |
| ^ | XOR | Sets bit to 1 if only one bit is 1. |
| ~ | NOT | Inverts all the bits. |
| << | Left Shift | Shifts bits left, filling with 0s (x << k is x * 2^k). |
| >> | Right Shift | Shifts bits right (floor(x / 2^k)). |
Bit Masks
A bit mask is a variable that helps you work with specific bits in another variable. It's a way to represent subsets or properties using the bits of an integer.
Common Operations (0-indexed from right)
- Check if k-th bit is set:
(mask & (1 << k)) != 0 - Set k-th bit to 1:
mask |= (1 << k) - Set k-th bit to 0:
mask &= ~(1 << k) - Toggle k-th bit:
mask ^= (1 << k) - Count set bits: In C++, use
__builtin_popcount(mask).
Applications
1. Representing Subsets:
An integer from 0 to 2ⁿ-1 can represent all 2ⁿ subsets of a set of n elements. The k-th bit is 1 if the k-th element is in the subset, and 0 otherwise.
# Python: Iterate through all subsets of {0, 1, ..., n-1}
for i in range(1 << n):
subset = []
for j in range(n):
if (i & (1 << j)):
subset.append(j)
# process subset
2. DP with Bitmasking:
This is a powerful technique for solving DP problems where the state needs to keep track of a subset of items. For example, in the Traveling Salesman Problem, the state could be dp[mask][last_city], where mask represents the set of visited cities.
3. Finding the Single Non-Repeating Number:
If an array contains numbers where every number appears twice except for one, you can find the unique one by XORing all the elements together. Since x ^ x = 0 and x ^ 0 = x, all the paired numbers will cancel out, leaving only the unique number.