Bit manipulation is a set of techniques for working directly with the binary representation of integers. This cheat sheet helps students recognize common bitwise operators, masks, shifts, and shortcuts used in algorithms. These skills are useful in systems programming, competitive programming, data compression, graphics, networking, and efficient problem solving.
Key Facts
- The expression x & mask keeps only the bits where mask has 1s and clears the bits where mask has 0s.
- The expression x | mask sets to 1 every bit where mask has a 1 while leaving other bits unchanged.
- The expression x ^ mask flips every bit where mask has a 1 and leaves unchanged every bit where mask has a 0.
- To test whether bit k is set, use (x & (1 << k)) != 0, where bit positions usually start at 0 from the right.
- To set bit k, use x = x | (1 << k), and to clear bit k, use x = x & ~(1 << k).
- Left shift multiplies by powers of two for non-overflowing nonnegative integers, so x << k equals x * 2^k.
- Right shift divides by powers of two for nonnegative integers using integer division, so x >> k equals floor(x / 2^k).
- A positive integer x is a power of two exactly when (x & (x - 1)) == 0.
Vocabulary
- Bit
- A bit is a single binary digit that can have the value 0 or 1.
- Mask
- A mask is a binary pattern used with bitwise operators to select, set, clear, or flip specific bits.
- Bitwise AND
- Bitwise AND, written &, compares bits and produces 1 only when both matching bits are 1.
- Bitwise OR
- Bitwise OR, written |, compares bits and produces 1 when at least one matching bit is 1.
- Bitwise XOR
- Bitwise XOR, written ^, compares bits and produces 1 when the matching bits are different.
- Shift
- A shift moves all bits left or right by a given number of positions, often multiplying or dividing by powers of two.
Common Mistakes to Avoid
- Using ^ for exponentiation is wrong in many programming languages because ^ usually means bitwise XOR, not power.
- Forgetting that bit positions start at 0 is wrong because the rightmost bit is bit 0, so 1 << 3 targets the fourth bit, not the third.
- Testing x & mask == 1 is often wrong because a set bit may produce values like 2, 4, or 8, so use (x & mask) != 0 instead.
- Clearing a bit with x & (1 << k) is wrong because that keeps only bit k; clearing requires x & ~(1 << k).
- Applying power-of-two tests to zero is wrong because (0 & -1) == 0, so the correct check is x > 0 and (x & (x - 1)) == 0.
Practice Questions
- 1 For x = 22, which is 10110 in binary, what is the value of x & 6, where 6 is 00110 in binary?
- 2 Use a bitwise expression to set bit 4 of x = 9, where bit positions start at 0, and find the new decimal value.
- 3 Determine whether 64 is a power of two using the test x > 0 and (x & (x - 1)) == 0.
- 4 Explain why bit masks are useful when a program needs to store several true or false settings inside one integer.