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.
Understanding Bit Manipulation Tricks Reference
A bit is a single storage place that holds zero or one. Larger integer types use a fixed number of these places, such as eight, sixteen, or thirty-two. This fixed width matters because a result that needs more space can lose its leftmost bits.
Unsigned values use every bit for size. Signed values usually use a system called two's complement, where the leftmost bit helps represent negative numbers.
A pattern that looks large when read as unsigned can mean a negative value when read as signed. Students should always know the integer type before predicting a result.
Bit operations treat a number like a row of independent switches. Each switch can represent a yes or no setting. Programs use this idea for permission flags, keyboard states, file properties, device settings, and game input.
One integer can hold many separate flags, which saves memory and makes checks fast. Bits can also store small values inside one larger value. This is called packing.
For example, a color pixel may keep red, green, and blue channel values in separate groups of bits. A mask acts like a stencil that selects one group while hiding the rest. After selecting a group, a shift can move it into the rightmost position so its ordinary numeric value can be read.
Shifts are useful because binary place values grow by factors of two. They appear in image processing, communication protocols, hash tables, and low-level hardware code. Their shortcut behavior has limits.
A left shift can overflow the available width, causing important bits to disappear. Shifting by an amount equal to or larger than the number of available bits may behave differently across programming languages. Right shifts need extra care for negative values.
Some languages copy the sign bit during a right shift, while others fill empty positions with zeros when using an unsigned type. Parentheses are important in longer expressions because arithmetic, comparisons, and bitwise operations do not always run in the order students expect.
Several common tricks work because subtracting one changes a number's lowest set bit and the zeros immediately to its right. This lets code locate, remove, or count set bits efficiently. Such patterns are common in algorithms that track subsets, choose available resources, or process binary trees.
They can be hard to read, so clear variable names and brief comments matter. When learning, write numbers in groups of four binary digits and trace every position by hand.
Test boundary cases such as zero, one, a value with one set bit, a value with many set bits, and the largest value for the chosen type. These checks reveal most mistakes with bit positions, signed values, and overflow.