Working with Bitsets: Setting and Testing Individual Bits

A bitset is a collection of bits that holds a fixed number of positions, and you can change or read the whole collection with a single expression. That convenience hides a risk. If you do not know exactly what each operator does to each position, a result that looks plausible can be wrong in ways that are hard to spot.

This article focuses on two families of operators. The bitwise operators combine or invert bits, one position at a time. The shift operators move every bit a given number of positions to the left or to the right. Once you can predict both families, you can read most bitset results without stepping through them by hand.

Think of a bitset as a row of slots. Each slot holds one bit, and every slot has a position. The left end of the bitset holds the bits that carry the most weight, and the right end holds the bits that carry the least. When you write a bitset as a pattern such as 1011, the leftmost character is the most significant position and the rightmost character is the least significant position.

The width of a bitset is the number of positions it holds. The width is fixed. That fixed width matters for every operation in this article, because a result is always read back into the same set of positions. Bits cannot grow beyond the edge, and the operators do not invent new positions to hold extra bits.

The complement operator ~ applies to a bitset as a whole and flips every bit. Each 0 becomes 1, and each 1 becomes 0. You do not need to look at positions one at a time to know the outcome, because the rule is the same at every position.

The AND operator & combines two bitsets position by position. At each position, the result bit is 1 only when both input bits at that position are 1. Other bitwise operators, such as OR and XOR, follow the same position-by-position pattern with their own rules. The source states that the usual bitwise operations can be applied to bitsets in this way.

Notice that the operator is the only thing that changed between the three rows. The inputs and the position-by-position reading stayed the same. When you choose an operator, you are choosing the rule that every position will follow, so pick the rule first and then read each position against it.

The source example makes a useful point about a bitset combined with its own complement. At every position, the complement holds the opposite of the original bit. An AND of a bit with its own opposite is always 0, because the two bits can never both be 1. So when a bitset is combined with its complement, every position of the result is 0, and the result is all zeros.

The shift operators move every bit of a bitset a given number of positions. The number after the operator sets how far the bits move. The shift operators shift in zeros, so the positions that open up on the vacated side are filled with 0. Bits that move past an edge of the fixed-width bitset are discarded rather than wrapped around to the other end.

A result diverges from what you might expect when you forget that the width is fixed. Because bits shifted past the edge are discarded, a shift never wraps bits around to the other end. Shifting 1011 left by one gives 0110 in a four-bit bitset, not 10110. The leftmost 1 is lost, and the result still has only four positions.

The complement is also bounded by the width. Complementing 1011 in a four-bit bitset gives 0100. The result never includes positions beyond the width of the set, so the complement describes exactly the positions the bitset owns and nothing more.

The source includes a short trace of bitset operations on a nine-bit bitset. Before you read the explanations for it, work through the trace line by line. For each line, write down the bit pattern you expect, then compare it with what the trace shows. Pay close attention to the direction the bits travel during a shift and to the value that fills the positions the shift opens up.