Bit twiddling

Through bitwise operations it is possible to work with the individual bits of a larger number, even though the architecture doesn’t allow bit-level addressing. Since we can’t use assignment to set individual bits, we have to be clever with whole-word operations and masks.

Some important identities

In order to isolate particular bits, it will be important to know, for each of the operations, what value can be safely used to ignore the bits we aren’t interested in, i.e. the operation’s identity element.

  • x & 1 == x

  • x | 0 == x

  • x ^ 0 == x

Looking at the truth table, you can work out what the non-identity element will do when combined with another bit.

  • x & 0 == 0

  • x | 1 == 1

  • x ^ 1 == ~x

Another XOR identity

Here’s another interesting identity.

  • x ^ x == 0

You see this pattern often in assembly, where for example xor rax, rax is used in preference to mov rax, 0 because it is encoded in less space and hardware is optimized to handle that case particularly quickly.

Masking

The above identities are per column of a bitwise operation. In order to get meaningful work done bitwise, it is necessary to construct a ‘mask’ specifying what to do in each bit position of a larger value. The conventional way to refer to bit positions is by the index, i.e. bit 0 is the one’s place (\(2^0=1\)), bit 1 is the two’s place, and so on; the largest place value in a 32-bit integer is bit 31.

To specify a value with a 1 in position \(n\) and 0 everywhere else, use bit shifting. Obviously 1 itself is the desired mask for bit 0, and 1 << n shifts that bit into any desired location (1 << 0 works and results, as you would hope, in 1).

The value you calculate with a 1 in the position(s) you want to affect is called a mask by analogy with a painter’s mask, where one tapes off the parts that shouldn’t get paint on them and leaves gaps where the paint can go through in exactly the desired shape.

Because 0 | 1 == 1, you can combine masks with OR (|) to get a mask with ones wherever any of the input masks had ones. So, to choose both bits 2 and 3, you could use a mask of (1 << 2) | (1 << 3).

Just as in decimal, a number written as a sequence of nines is one less than a power of ten (e.g. \(999 = 10^3 - 1\)), in binary a number written as a sequence of ones is one less than a power of two (e.g. \(111_2 = 2^3 - 1\)). You can use this fact to quickly generate a mask that selects all of the bits up to (not including) \(n\) with the expression (1 << n) - 1. Of course, you can also shift that into any position you want, so to select 4 bits starting above bit 3 (i.e. bits 4–7) you could mask with ((1 << 4) - 1) << 3.

These sorts of shifting expressions are ideally suited for computing masks at runtime, when some of the parameters are variables, or to state the programmer’s intention clearly. When the mask is known at compile time, it is common to simply write the number out in hexadecimal. (Writing it out in binary might be even clearer, but hexadecimal is shorter and C didn’t support binary literals until 2014.) So, the equivalent mask that could be computed to mask bits 4–7 could also be written immediately as 0x78.

Manipulating bits

If you want to calculate x but with some addition bits turned on as indicated by the ones in a mask, choose the operation where the result can be guaranteed to be 1, i.e. OR. You can calculate the result with x | mask, but you very often want to store the result back into x. Although x = x | mask is adequate, C provides augmented assignment operators for most of the binary operators, so it would be more idiomatic to write the following.

/* turn on the bits specified by mask */
x |= mask;

To toggle (i.e. invert) the masked bits, use XOR.

/* toggle the bits specified by mask */
x ^= mask;

To turn selected bits off, the operation we need is AND, but the usual mask with ones to select the bits is the exact opposite of what we need: ones where the operation is to leave bits alone, and zeroes where the bits are to be suppressed. Fortunately, ‘exact opposite’ is an operation we have—bitwise NOT.

/* turn off the bits specified by mask */
x &= ~mask;

Turning bits on and off and toggling them are all useful, but in the end, one generally wants to check what the results have been. To see whether bits are set, you can exploit the usual Boolean truthiness rule since a number with any bits set is true; just turn off all of the bits you aren’t interested in.

/* do something if any of the bits specified by mask are on */
if (x & mask)
    something();

Any bits remaining set will count as true; if you want to check whether all of a set of bits are set, you will need to mask and test them separately, and combine the results with the usual logical &&.

You have attempted of activities on this page