--- title: 'Bit-Level Operations' source: 'https://academia.sh/en/courses/how-computers-work/bit-level-operations' course: 'How Computers Work' language: en updated: '2026-08-17T18:08:07+00:00' license: 'CC BY-SA 4.0' --- # Bit-Level Operations The AND, OR, XOR, and NOT operators, shifts, and field extraction with masks. 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. ```python 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: ```python 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.