Bit-Level Operations

Previous lessons always interpreted bit patterns as a whole: thirty-two bits together formed an integer or a real number. Programs, however, frequently work with parts of a pattern — extracting a single byte, turning on a flag, clearing a field.

This lesson covers the operators that perform these part-level operations. They are among the cheapest operations in hardware, and a large share of low-level code is written with them.

Bitwise Logical Operators

Four basic operators are defined by their truth tables over bits. The operators apply bit by bit: the $i$-th bit of the result depends only on the $i$-th bits of the inputs.

$a$	$b$	$a \mathbin{\&} b$ (AND)	$a \mid b$ (OR)	$a \oplus b$ (XOR)
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

The NOT operator takes a single input and flips every bit: $\lnot 0 = 1$, $\lnot 1 = 0$.

Over two eight-bit patterns:

  1100 1010        1100 1010        1100 1010
& 1010 0110      | 1010 0110      ^ 1010 0110
-----------      -----------      -----------
  1000 0010        1110 1110        0110 1100

Each operator has a distinguishing use:

• AND clears unwanted bits: every bit facing a $0$ is erased.
• OR turns on desired bits: every bit facing a $1$ is set.
• XOR flips selected bits, and is also the bit-level answer to “are these different?” A number XORed with itself is zero, which means XORing the same value twice returns to the starting value.

These operators must not be confused with the logical and/or operators. Logical operators treat an entire value as true or false and short-circuit in most languages; bit-level operators process each bit independently and never short-circuit.

Shifting

Left shift (<<) moves every bit to the left, filling from the right with zeros. Since each shift doubles the positional values, it multiplies the number by two:

$$\texttt{0000 0101} \ll 2 = \texttt{0001 0100} \qquad (5 \times 4 = 20)$$

Right shift (>>) moves bits to the right and divides the number by two, discarding the fractional part. Which bit fills in from the left depends on how the value is interpreted:

• Logical shift fills from the left with zero; correct for unsigned values.
• Arithmetic shift fills from the left with a copy of the sign bit; it preserves the sign of signed values.

This distinction is the same one as the sign-extension rule from the previous lesson. In Python, integers are signed and >> behaves arithmetically: -8 >> 1 gives -4, -5 >> 1 gives -3 (the result rounds down, not toward zero).

In fixed-width languages, shifting by a count equal to or greater than the data width is undefined behavior; shifting a 32-bit value 32 times does not give a portable result. This is one of the known sources of code that fails silently.

Masking

A mask is a fixed pattern that states which bits are of interest. Four basic operations are performed with a mask:

Purpose	Operation	Description
Test a bit	value & mask	If the result is nonzero, the bit is set
Set a bit	value | mask	Bits equal to $1$ in the mask are turned on
Clear a bit	value & ~mask	Bits equal to $1$ in the mask are zeroed
Flip a bit	value ^ mask	Bits equal to $1$ in the mask are flipped

Extracting a field is two steps: shift the field all the way to the right, then mask off the excess. Taking the second byte from the course’s shared example:

$$(\texttt{0x41424344} \gg 16)\ \&\ \texttt{0xFF} = \texttt{0x42}$$

The shift amount states how many bits from the right the field begins; the mask states how many bits wide the field is. 0xFF selects an eight-bit field, 0x0F a four-bit field, 0x01 a single-bit field.

The same method works in reverse as well: to write a value into a field, the field is first cleared, then the new value is shifted and placed with OR.

Flag Sets

Independent on/off options can each be assigned to a bit. This arrangement carries many options in a single integer and makes combining and testing options cheap.

READ    = 0b100      # 4
WRITE   = 0b010      # 2
EXECUTE = 0b001      # 1

permission = READ | WRITE          # 0b110 = 6

print(bool(permission & WRITE))    # True   — is write permission set?
print(bool(permission & EXECUTE))  # False

permission |= EXECUTE              # add execute permission   -> 0b111
permission &= ~WRITE               # remove write permission  -> 0b101
print(f"{permission:03b}")         # 101

The three bits in this example are exactly the file permissions written in octal notation in the second lesson: the pattern 0b101 is 5, that is, the permission r-x. The reason octal notation is preferred in that domain is that groups of three bits map directly to a single digit.

Common Idioms

A few patterns built from bit operators recur frequently in source code:

• x & (x - 1) — clears the rightmost set bit. If the result is zero, $x$ is a power of two (only one bit was set). The same expression, used in a loop, counts set bits.
• x & -x — leaves only the rightmost set bit. This follows from the definition of negation in two’s complement.
• x << k and x >> k — multiplication and division by powers of two. Compilers already perform this transformation; writing a shift in source code does not improve performance and only reduces readability.
• x ^ mask — flips selected bits; x ^ x is always zero.

The following program shows two of these idioms together with field extraction:

def is_power_of_two(x: int) -> bool:
    """A positive x is a power of two if exactly one bit is set."""
    return x > 0 and (x & (x - 1)) == 0


def count_set_bits(x: int) -> int:
    """Counts by clearing the rightmost set bit at each step."""
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count


value = 0x41424344
bytes_ = [(value >> k) & 0xFF for k in (24, 16, 8, 0)]

print([hex(b) for b in bytes_])         # ['0x41', '0x42', '0x43', '0x44']
print(is_power_of_two(64))              # True
print(is_power_of_two(48))              # False
print(count_set_bits(value))            # 9
print(bin(value).count("1"))            # 9  — same result, different route

The loop in count_set_bits runs once per set bit, not once per bit of width. The pattern 0x41424344 has nine set bits (0x41 and 0x42 contribute two each, 0x43 three, 0x44 two), so the loop runs nine times rather than thirty-two.

Summary

• Bit-level operators process each bit independently; unlike logical operators, they do not treat the entire value as true or false.
• AND clears bits, OR sets bits, XOR flips bits; a value XORed with itself is zero.
• Left shift multiplies by two; right shift divides by two, and the fill rule from the left depends on whether the value is interpreted as signed.
• Field extraction is two steps: shift the field right, then apply a mask the width of the field.
• Independent options can be carried as flag bits in a single integer; combining uses OR, testing uses AND.
• x & (x - 1) clears the rightmost set bit; the power-of-two test and bit counting are both built on this idiom.

Next Step

Representation rules for numbers are now complete. Text raises a different problem: letters are not naturally numbers, so every character must be mapped to a number, and this mapping has to be agreed upon worldwide. The next lesson takes up how that agreement is built, and why the difference between a code point and a byte sequence matters.