Bit Masking
Bit masking is the technique of using a bitmask to represent a set of flags or states. Each bit in the mask corresponds to a specific item. We use bitwise operations to set, clear, toggle, or test bits.
Common operations:
// Assume we have 4 flags (bits 0-3)
int mask = 0;
// Set bit at position k (0-indexed)
mask |= (1 << k);
// Clear bit at position k
mask &= ~(1 << k);
// Toggle bit at position k
mask ^= (1 << k);
// Check if bit at position k is set
boolean isSet = (mask & (1 << k)) != 0;
Bit masks are used in DP on subsets, representing permutations, and compactly storing boolean states.
Two Minute Drill
- Bitmask: an integer where each bit represents a flag or element.
- Set: mask | (1 << k)
- Clear: mask & ~(1 << k)
- Toggle: mask ^ (1 << k)
- Test: (mask & (1 << k)) != 0
- Useful for subset DP and state compression.
Need more clarification?
Drop us an email at career@quipoinfotech.com