Bit Manipulation
Use binary representations and bitwise operators for masks, flags, and compact state.
uint32_t from stdint.h; this makes the width explicit and avoids many surprises from signed shifts.Objectives: represent and update compact flags
A bit is a binary digit, either zero or one. In an unsigned integer, bitwise operations act independently on corresponding bit positions. Bitmasks are useful for compact flags, small sets of options, subset enumeration, and state compression. They are not automatically faster or clearer than an array or set—use them when the finite domain and width make the representation appropriate.
1. Binary place values and core operators
For an unsigned value, bit position 0 is the least significant bit and has value 2⁰; position 1 has value 2¹, and so on. AND (&) keeps a bit only when both inputs have it set. OR (|) sets a bit when either input has it set. XOR (^) sets a bit when the inputs differ. NOT (~) flips every bit in the integer type’s width, so it is often best used with an explicit mask.
| Operator | Meaning | Common use |
|---|---|---|
| a & b | Set only where both bits are 1 | Test selected bits or keep a mask |
| a | b | Set where either bit is 1 | Set one or more flags |
| a ^ b | Set where bits differ | Toggle a bit; parity/XOR reductions |
| a << k | Shift bits left by k positions | Form a bit mask or scale unsigned values |
| a >> k | Shift bits right by k positions | Inspect lower/higher portions of unsigned values |
2. Set, clear, toggle, and test one bit
Build a one-bit mask by shifting the unsigned value 1 to the desired position. OR sets that bit; AND with the complement clears it; XOR toggles it. AND with the mask tests whether it is set. The caller must guarantee that the bit index is in the valid range 0 through 31.
For production interfaces, validate bit < 32 before shifting. In C, shifting by a count greater than or equal to the operand width is undefined behavior. Use unsigned fixed-width values for masks; right-shifting a negative signed integer can be implementation-defined, and left-shifting signed values can overflow with undefined behavior.
3. Masks as small sets
When there are at most 32 distinct options, bit i can represent whether option i is present. A subset can be inserted or removed with the same set/clear operations. To check whether all required flags are set, compare (mask & required) == required; to check whether any are set, compare the result to zero. This representation makes union and intersection direct, but it does not preserve order or repeated items.
The XOR reduction returns the unique value only under a precise contract: exactly one unsigned value appears once and every other value appears exactly twice; XOR is bitwise, so cancellation is exact. It does not solve the same task when duplicates appear arbitrary numbers of times. For sets with a larger or dynamic universe, use an appropriate set or bitset abstraction rather than overflowing this fixed-width mask.
4. Count set bits and test powers of two
Kernighan’s identity clears the lowest set bit each iteration: for nonzero unsigned x, x & (x − 1) is x with its least significant 1 removed. Therefore the loop count equals the number of set bits, also called the population count. A nonzero power of two has exactly one set bit; this identity gives a compact test.
The count runs in O(number of set bits), at most 32 iterations for a 32-bit value. Some platforms provide hardware-backed population-count instructions or compiler/library helpers; use a portable interface appropriate for the project instead of assuming a non-standard builtin exists.
5. Enumerate subsets with a bitmask
For n options, each integer mask from zero through 2ⁿ−1 represents one subset. If bit i is set, item i is included. This technique is useful for exhaustive search when n is deliberately small; the number of subsets doubles each time n increases by one, so it does not make an exponential problem scalable by itself. Keep the number of bits within the mask width.
The guard makes both the shift and the amount of work explicit. This example uses a smaller limit than the full type width because generating millions of subsets quickly becomes impractical. Empty mask zero represents the empty subset; the final mask has every option present.
6. Precedence and signedness deserve attention
Parenthesize bitwise expressions even when operator precedence is known. In C, equality operators bind more tightly than bitwise AND, so value & mask == mask is parsed differently from the intended all-bits test. Write (value & mask) == mask. Also prefer explicit unsigned constants and types; integer promotions can make small integer operands behave as int.
For a collection of named flags, declare the position and construct masks once instead of scattering numeric literals. Keep unrelated flag groups separate, define which bits may be set, and mask off reserved bits when importing a value from a file or network packet. This makes changes easier to review and prevents an unknown flag from silently changing behavior.
1 << 17 throughout application code.7. Common mistakes
- Shifting a signed 1: high-bit shifts can overflow or be undefined. Use a fixed-width unsigned value and a valid shift count.
- Forgetting to parenthesize a test: equality binds tighter than bitwise AND in C; write
(x & mask) != 0. - Assuming NOT flips only meaningful flags:
~maskflips every bit in the type. AND with an explicit allowed-bits mask when needed. - Using a bitmask for an unbounded set: a fixed-width integer has a strict limit and no duplicate/order semantics.
8. Practice
- Implement a helper that toggles a validated flag and returns an error for an index outside 0…31.
- Given two permission masks, determine whether the user has every required permission and whether any optional permission is granted.
- Count set bits using the simple shift-and-test loop; compare its iteration count to Kernighan’s method for sparse and dense inputs.
- Enumerate all subsets of a collection of n ≤ 20 items using a mask. Explain the time and memory growth.
- Prove why XOR cancels paired values, then construct a counterexample when one duplicate occurs three times.
🎯 Key Takeaways
- ✓Bitwise operators work on individual positions of integer representations.
- ✓A mask lets an unsigned integer represent a fixed set of flags.
- ✓Set, clear, toggle, and test use OR, AND, XOR, and AND respectively.
- ✓Validate shift width and use explicit unsigned types to avoid undefined behavior.
- ✓Parenthesize expressions because C operator precedence can change their meaning.
- ✓Bitmasks are effective only when the domain fits and their semantics stay clear.
Next
Move from compact state to range queries with dedicated tree structures.
HELP US IMPROVE
How was this lesson?
Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
