--- title: Boolean Algebra and Bit Manipulation module: Foundations moduleNumber: 0 lessonNumber: 5 order: 5 summary: > Treat a word as a vector of independent bits and the bitwise operators become an algebra. We define AND, OR, NOT, and XOR as bit vectors, build the masking idioms that set, clear, toggle, and test individual bits, extract fields with zero- and sign-extension, count set bits three ways, derive the classic x & (x - 1) family of tricks, and distinguish bitwise operators from C's short-circuiting logical operators. topics: [Foundations] sources: - book: Bryant & O'Hallaron ref: "CS:APP — §2.1.6–2.1.9 Boolean Algebra and Bit-Level Operations" --- So far a word has been a _number_. This lesson reads it as something simpler: a vector of $w$ independent bits, each a truth value, with operations applied to every position at once. That view turns a register into a set of flags and the bitwise operators into an algebra for manipulating them — the language of permission bits, hardware control registers, color channels, and bitmaps. Building on [bits and bytes](/computer-architecture/foundations/bits-bytes-and-words), this final foundations lesson covers the four logical operations, the masking idioms, and the difference between C's bitwise and logical operators. ## The four operations as bit vectors Each operator is defined first on single bits by a truth table, then lifted to a $w$-bit word by applying it **independently to each position** — bit $i$ of the result depends only on bit $i$ of the inputs. $$ % caption: Truth tables for the four bitwise operations on single bits. AND is 1 % caption: only when both inputs are 1; OR when either is; XOR when they differ; % caption: NOT flips its one input. \begin{tikzpicture}[font=\footnotesize, cell/.style={draw, minimum size=6mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % AND block at x=0 \node[text=acc] at (0.6,2.5) {AND \&}; \foreach \r/\a/\b/\o in {0/0/0/0, 1/0/1/0, 2/1/0/0, 3/1/1/1} { \node[cell] at (0,1.8-\r*0.6) {\a}; \node[cell] at (0.6,1.8-\r*0.6) {\b}; \node[cell, fill=acc!8] at (1.2,1.8-\r*0.6) {\o}; } % OR block at x=2.6 \node[text=acc] at (3.1,2.5) {OR}; \draw[acc, line width=0.8pt] (3.62,2.32) -- (3.62,2.68); \foreach \r/\a/\b/\o in {0/0/0/0, 1/0/1/1, 2/1/0/1, 3/1/1/1} { \node[cell] at (2.6,1.8-\r*0.6) {\a}; \node[cell] at (3.2,1.8-\r*0.6) {\b}; \node[cell, fill=acc!8] at (3.8,1.8-\r*0.6) {\o}; } % XOR block at x=5.2 \node[text=acc] at (5.8,2.5) {XOR \^{}}; \foreach \r/\a/\b/\o in {0/0/0/0, 1/0/1/1, 2/1/0/1, 3/1/1/0} { \node[cell] at (5.2,1.8-\r*0.6) {\a}; \node[cell] at (5.8,1.8-\r*0.6) {\b}; \node[cell, fill=acc!8] at (6.4,1.8-\r*0.6) {\o}; } % NOT block at x=7.8 \node[text=acc] at (8.1,2.5) {NOT \~{}}; \foreach \r/\a/\o in {0/0/1, 1/1/0} { \node[cell] at (7.8,1.8-\r*0.6) {\a}; \node[cell, fill=acc!8] at (8.4,1.8-\r*0.6) {\o}; } \end{tikzpicture} $$ Read on full words, the four become parallel operations over all $w$ lanes. With $a = \mathtt{0x69} = 0110\,1001$ and $b = \mathtt{0x55} = 0101\,0101$: | Op | C | Result on $a, b$ | Hex | | --- | --- | --- | --- | | AND | `a & b` | $0100\,0001$ | `0x41` | | OR | `a \| b` | $0111\,1101$ | `0x7d` | | XOR | `a ^ b` | $0011\,1100$ | `0x3c` | | NOT | `~a` | $1001\,0110$ | `0x96` | These operations form a **Boolean algebra**: AND and OR distribute over each other, both are commutative and associative, and complementation obeys the laws below. XOR is addition modulo 2, which makes it its own inverse — $a \oplus a = 0$ and $a \oplus 0 = a$ — the property behind the in-place swap and many checksum tricks. ## Masking: addressing one bit at a time A **mask** is a constant chosen so a bitwise operation touches exactly the bits we mean and leaves the rest alone. The four idioms cover everything you can do to an individual bit, each pairing an operator with the mask $\mathtt{1} \ll k$ (a single $1$ in position $k$): - **Set** bit $k$: `x | (1 << k)`: OR forces a $1$ where the mask is $1$, leaves the rest unchanged (OR with $0$ is identity). - **Clear** bit $k$: `x & ~(1 << k)`: AND with a $0$ forces that position to $0$; the inverted mask is $1$ everywhere else, so the rest survive. - **Toggle** bit $k$: `x ^ (1 << k)`: XOR with $1$ flips, XOR with $0$ keeps. - **Test** bit $k$: `(x >> k) & 1` or `x & (1 << k)`: isolate the bit and check if it is nonzero. $$ % caption: Clearing the low nibble of a byte by ANDing with the mask 1111 0000. % caption: Where the mask is 1 the input bit survives; where it is 0 the result bit % caption: is forced to 0, regardless of the input. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=7mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\v in {0/1,1/0,2/1,3/1,4/1,5/0,6/0,7/1} \node[bit] at (\i*0.8,1.6) {\v}; \node[anchor=east] at (-0.55,1.6) {value}; \foreach \i/\v in {0/1,1/1,2/1,3/1,4/0,5/0,6/0,7/0} \node[bit, draw=acc, text=acc] at (\i*0.8,0.55) {\v}; \node[anchor=east, text=acc] at (-0.55,0.55) {mask}; \foreach \i/\v in {0/1,1/0,2/1,3/1,4/0,5/0,6/0,7/0} \node[bit, fill=acc!8] at (\i*0.8,-0.55) {\v}; \node[anchor=east] at (-0.55,-0.55) {\& result}; \node[anchor=west] at (6.1,-0.55) {low nibble cleared}; \end{tikzpicture} $$ A mask need not be a single bit. `0xFF` isolates a byte, `0x0F` a nibble, and `(1 << n) - 1` produces $n$ ones in the low positions, the standard way to keep just the low $n$ bits of a value. The C code below packages the four single-bit idioms. ```c [bitops.c] /* operate on bit k of x (0 = least significant) */ unsigned set_bit (unsigned x, int k) { return x | (1u << k); } unsigned clr_bit (unsigned x, int k) { return x & ~(1u << k); } unsigned tog_bit (unsigned x, int k) { return x ^ (1u << k); } int test_bit (unsigned x, int k) { return (x >> k) & 1u; } /* keep only the low n bits */ unsigned low_n (unsigned x, int n) { return x & ((1u << n) - 1); } ``` > **Definition (Mask).** A constant bit vector used with a bitwise operator to > select which positions an operation affects. AND with a mask clears the $0$ > positions; OR sets the $1$ positions; XOR toggles the $1$ positions; the others > pass through unchanged. ## Extracting fields: zero-extend or sign-extend Packing several small fields into one word is the other half of masking: pulling a field back _out_ combines a shift with a mask, and the subtlety is what fills the high bits afterward. `(x >> 8) & 0xff` isolates byte 1 of `x`, and the AND leaves zeros above it, so the extracted field is **zero-extended**, which is correct exactly when the field is unsigned. If the packed field is a _signed_ quantity, zero extension corrupts it: the field's own sign bit ends up buried mid-word with zeros above, and a negative field reads as a large positive number. The fix is the shift pair: push the field's top bit into the word's sign position with a left shift, then let an arithmetic right shift drag copies of it back down: ```c [extract.c] unsigned x = 0x1234abcd; unsigned uf = x & 0xff; /* 0x000000cd = 205: zero-extended */ int sf = ((int)(x << 24)) >> 24; /* 0xffffffcd = -51: sign-extended */ ``` The byte is `0xcd`, which as a signed 8-bit value is $-51$ (recall [truncation](/computer-architecture/foundations/integer-representation): the top bit of the narrow width is its sign bit). After `x << 24` the word is `0xcd000000` with the field's sign bit at position 31; the arithmetic shift back replicates it, producing `0xffffffcd`, the correct 32-bit $-51$. C only guarantees an arithmetic right shift on signed types in practice rather than by the letter of the standard, but every mainstream compiler and every x86-64 and ARM machine provides it, and the idiom is how compilers themselves widen packed signed fields. ## De Morgan's laws The complement turns AND into OR and back, the two **De Morgan's laws**, which hold position-by-position and so apply to whole words at once: $$ \sim\!(a \,\&\, b) = \;\sim\! a \;|\; \sim\! b, \qquad \sim\!(a \;|\; b) = \;\sim\! a \;\&\; \sim\! b. $$ They let you rewrite a "neither/nor" as a "not-this and not-that," and they are the reason any logic gate network can be built from NANDs or NORs alone. A quick check on $a = 1100$, $b = 1010$: $\sim\!(a \,\&\, b) = \sim\! 1000 = 0111$, and $\sim\! a \,|\, \sim\! b = 0011 \,|\, 0101 = 0111$ — equal, as promised. ## Bitwise versus logical operators C has two families that look almost alike and behave completely differently. The **bitwise** operators `&`, `|`, `~`, `^` work on every bit of their operands, as above. The **logical** operators `&&`, `||`, `!` treat each operand as a single truth value (zero is false, _any_ nonzero value is true) and always yield $0$ or $1$. $$ % caption: The same operands through bitwise & versus logical &&. Bitwise ANDs % caption: each lane to 0x00; logical reads both operands as "true" and yields 1. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=6.5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % bitwise row: 0x55 & 0xAA = 0x00 \node[anchor=east] at (-0.3,1.5) {\texttt{0x55 \& 0xAA}}; \foreach \i/\v in {0/0,1/1,2/0,3/1,4/0,5/1,6/0,7/1} \node[bit] at (\i*0.7+0.3,1.5) {\v}; \node at (6.0,1.5) {$\Rightarrow$}; \foreach \i/\v in {0/0,1/0,2/0,3/0,4/0,5/0,6/0,7/0} \node[bit, fill=acc!8] at (\i*0.7+6.6,1.5) {\v}; \node[anchor=west] at (12.3,1.5) {\texttt{= 0x00}}; % logical row: 0x55 && 0xAA = 1 \node[anchor=east] at (-0.3,0.2) {\texttt{0x55 \&\& 0xAA}}; \node[bit, draw=acc, text=acc] at (0.3,0.2) {T}; \node at (1.3,0.2) {and}; \node[bit, draw=acc, text=acc] at (2.3,0.2) {T}; \node at (3.5,0.2) {$\Rightarrow$}; \node[bit, fill=acc!8] at (4.6,0.2) {1}; \end{tikzpicture} $$ The figure shows the danger: `0x55 & 0xAA` is $0$ (the two patterns share no bit), but `0x55 && 0xAA` is $1$ (both are nonzero, hence both true). Beyond the result, the logical operators **short-circuit** — `a && b` never evaluates `b` if `a` is false, and `a || b` skips `b` if `a` is true — which the bitwise operators never do. Writing `&` where you meant `&&` can both compute the wrong value and trigger a side effect that should have been skipped. ```c [logic_vs_bitwise.c] int a = 0x55, b = 0xAA; int band = a & b; /* 0x00 : per-bit AND, no shared bits */ int land = a && b; /* 1 : both nonzero, so "true && true" */ /* short-circuit: p is not dereferenced when p is NULL */ if (p != NULL && p->len > 0) { /* safe */ } /* if (p != NULL & p->len > 0) would dereference NULL */ ``` ## The x - 1 family, derived The most-quoted interview tricks all trace back to one observation about what subtracting $1$ does to a bit pattern. Any nonzero $x$ ends in its lowest set bit followed by some run of zeros: $\ldots 1\underbrace{00\ldots0}_{k}$. Subtracting $1$ borrows through that run — the trailing zeros flip to ones, the lowest set bit flips to zero, and **everything above it is untouched**: $$ % caption: Subtracting 1 from x = 104 borrows through the trailing zeros (bits % caption: 0..2) and clears the lowest set bit (bit 3); bits above are untouched. % caption: ANDing x with x - 1 therefore erases exactly that lowest set bit. \begin{tikzpicture}[font=\footnotesize, bit/.style={draw, minimum size=6.5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[anchor=east] at (-0.5,1.8) {x = 104}; \foreach \i/\v in {0/0,1/1,2/1,3/0} \node[bit] at (\i*0.7,1.8) {\v}; \foreach \i/\v in {4/1,5/0,6/0,7/0} \node[bit, draw=acc, text=acc] at (\i*0.7,1.8) {\v}; \node[anchor=east] at (-0.5,0.9) {x - 1 = 103}; \foreach \i/\v in {0/0,1/1,2/1,3/0} \node[bit] at (\i*0.7,0.9) {\v}; \foreach \i/\v in {4/0,5/1,6/1,7/1} \node[bit, draw=acc, text=acc] at (\i*0.7,0.9) {\v}; \node[anchor=east] at (-0.5,0.0) {x \& (x - 1)}; \foreach \i/\v in {0/0,1/1,2/1,3/0,4/0,5/0,6/0,7/0} \node[bit, fill=acc!8] at (\i*0.7,0.0) {\v}; \node[anchor=west] at (5.35,0.0) {= 96: lowest 1 gone}; \node[text=acc, anchor=north] at (3.85,-0.45) {borrow region}; \end{tikzpicture} $$ Everything else in the family is a corollary. - **Clear the lowest set bit**: `x & (x - 1)`. The two operands agree everywhere except across the borrow region, and inside it they share no set bit. - **Power-of-two test**: `x && !(x & (x - 1))`. A power of two has exactly one set bit, so clearing it leaves zero; the `x &&` guard rejects zero itself. - **Isolate the lowest set bit**: `x & -x`. Negation is complement-plus-one, and that final $+1$ carries through the complemented trailing ones back up to the position of the lowest set bit. So $-x$ agrees with $x$ at that one bit, disagrees everywhere above it, and is zero below: the AND keeps exactly one bit. For $x = 104 = 0110\,1000$: $-x = 1001\,1000$, and the AND is $0000\,1000 = 8$. - **Opposite-sign test**: `(x ^ y) < 0`. Bit 31 of the XOR is the XOR of the two sign bits, so the result is negative exactly when the signs differ — no overflow-prone subtraction involved. - **Round up to a multiple of $2^k$**: `(x + (1 << k) - 1) & ~((1 << k) - 1)`. Adding $2^k - 1$ pushes any non-multiple past the next boundary, and the AND snaps back down to it — the same bias pattern as [signed division](/computer-architecture/foundations/integer-arithmetic), and the standard way to align a size or an address. ```c [tricks.c] int is_pow2 = x && !(x & (x - 1)); /* nonzero, single bit set */ unsigned lowest = x & (~x + 1); /* isolate lowest set bit */ int differ = (x ^ y) < 0; /* signs differ */ size_t aligned = (n + 7) & ~7u; /* round n up to 8 bytes */ a ^= b; b ^= a; a ^= b; /* swap with no temporary */ ``` The last line swaps two values with no temporary, because XOR is associative and its own inverse: after the first step `a` holds $a \oplus b$; the second sets `b` to $(a \oplus b) \oplus b = a$; the third sets `a` to $(a \oplus b) \oplus a = b$. It is more a demonstration of the algebra than a speed win — a compiler handles a normal swap at least as well — but it shows how the operations compose.[^tricks] ## Counting set bits **Population count**, how many bits of a word are $1$, shows up everywhere bits are used as sets: Hamming distance, bitboards, sparse-index bookkeeping. Three approaches, in increasing cleverness: - **Shift-and-test**: loop over all $w$ positions, adding `x & 1` and shifting. Always $w$ iterations. - **Kernighan's loop**: repeatedly clear the lowest set bit with `x &= x - 1`, counting iterations. Runs once _per set bit_, so a sparse word finishes early. - **Divide and conquer**: add neighbors in parallel lanes (first $16$ pairs of adjacent bits, then $8$ pairs of 2-bit counts, then $4$ pairs of 4-bit counts), using masks to keep the lanes from bleeding into each other. Constant time, no loop, and the pattern generalizes to any width. $$ % caption: Divide-and-conquer popcount on the byte 1011 0110. Adjacent bits sum % caption: into 2-bit counts, adjacent counts into 4-bit counts, and one final % caption: add yields 5, every addition running in parallel lanes of one word. \begin{tikzpicture}[font=\footnotesize, >=stealth, bit/.style={draw, minimum size=6mm, inner sep=0pt}, grp/.style={draw, minimum height=6mm, minimum width=10mm, inner sep=2pt}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\v in {0/1,1/0,2/1,3/1,4/0,5/1,6/1,7/0} \node[bit] at (\i*0.7,2.7) {\v}; \foreach \x in {0.35, 1.75, 3.15, 4.55} \draw[->, black] (\x,2.35) -- (\x,1.82); \foreach \x/\v in {0.35/01, 1.75/10, 3.15/01, 4.55/01} \node[grp] at (\x,1.5) {\v}; \node[anchor=west, black] at (5.5,1.5) {2-bit counts: 1, 2, 1, 1}; \draw[->, black] (0.35,1.18) -- (0.95,0.65); \draw[->, black] (1.75,1.18) -- (1.15,0.65); \draw[->, black] (3.15,1.18) -- (3.75,0.65); \draw[->, black] (4.55,1.18) -- (3.95,0.65); \node[grp, minimum width=14mm] at (1.05,0.3) {0011}; \node[grp, minimum width=14mm] at (3.85,0.3) {0010}; \node[anchor=west, black] at (5.5,0.3) {4-bit counts: 3, 2}; \draw[->, black] (1.05,-0.02) -- (2.25,-0.55); \draw[->, black] (3.85,-0.02) -- (2.65,-0.55); \node[grp, minimum width=20mm, fill=acc!8] at (2.45,-0.9) {0000 0101}; \node[anchor=west, text=acc] at (5.5,-0.9) {= 5 set bits}; \end{tikzpicture} $$ ```c [popcount.c] /* Kernighan: one iteration per set bit */ int pop_kernighan(unsigned x) { int n = 0; while (x) { x &= x - 1; n++; } return n; } /* divide and conquer: five parallel steps, no loop */ int pop_parallel(unsigned x) { x = (x & 0x55555555) + ((x >> 1) & 0x55555555); /* pairs */ x = (x & 0x33333333) + ((x >> 2) & 0x33333333); /* nibbles */ x = (x + (x >> 4)) & 0x0f0f0f0f; /* bytes */ return (x * 0x01010101) >> 24; /* sum bytes */ } ``` The mask `0x55555555` is alternating `01` lanes; AND-ing `x` and `x >> 1` with it lines up each bit pair as two 2-bit numbers, and the add produces all sixteen pair-counts in one instruction. Each later step doubles the lane width. The final multiply by `0x01010101` folds the four byte-counts into the top byte: a popcount in about five arithmetic instructions, and the reason this is a classic puzzle rather than a practical need is that modern ISAs provide it in hardware as a single instruction (`popcnt` on x86-64).[^pop] ## Bit-parallelism in real systems The divide-and-conquer popcount above is one instance of a broader technique that CS:APP touches only through its puzzles: **SWAR**, "SIMD within a register," where a single wide register is treated as several independent lanes and one ordinary arithmetic instruction operates on all of them at once. The popcount masks `0x55...`, `0x33...`, `0x0f...` act as lane separators — they keep each sub-count from carrying into its neighbor. The same idea counts trailing zeros, finds a zero byte inside a word (the trick `strlen` uses to test eight bytes per iteration), and compares packed values, all with no special vector hardware.[^swar] Where the data genuinely is a set of independent lanes, dedicated SIMD instruction sets — SSE and AVX on x86-64, NEON on ARM — take the idea further, operating on 128, 256, or 512 bits at a time; SWAR is the version that needs nothing but the integer ALU already in front of you. $$ % caption: SWAR: one 32-bit register as four independent 8-bit lanes. A single add % caption: operates on all four at once, but a carry out of one lane would corrupt % caption: its neighbor, so lane-separator masks (like the popcount masks) confine % caption: each operation to its own lane. \begin{tikzpicture}[font=\footnotesize, >=stealth, lane/.style={draw, minimum width=18mm, minimum height=8mm, inner sep=2pt, align=center}] \definecolor{acc}{HTML}{2348F2} \node[lane] at (0,0) {lane 3}; \node[lane] at (1.9,0) {lane 2}; \node[lane] at (3.8,0) {lane 1}; \node[lane] at (5.7,0) {lane 0}; \node[anchor=west] at (7.1,0) {one 32-bit register}; \foreach \x in {0.95, 2.85, 4.75} \draw[acc, thick] (\x,-0.5) -- (\x,0.5); \node[text=acc, anchor=north, font=\scriptsize] at (2.85,-0.55) {masks keep carries f\/rom crossing these lines}; \end{tikzpicture} $$ These techniques underpin data structures you meet later. A **bitboard** represents a chessboard or a game state as a 64-bit word, one bit per square, so that moving a whole rank of pieces is one shift and testing an attack is one AND. A **Bloom filter** stores a set as a bit array and tests membership with a handful of masked bit-tests, trading a small false-positive rate for a fraction of the memory a hash set would use. Even the [page tables](/computer-architecture/virtual-memory/the-tlb-and-multi-level-page-tables) elsewhere in this course extract index fields with exactly the shift-and-mask idiom from earlier in this lesson. The bit-level algebra underlies any code that treats memory as a set of flags rather than a list of numbers. > **Takeaway.** A word is a vector of bits, and the bitwise operators `& | ~ ^` act > on every position at once, forming a Boolean algebra with De Morgan's laws. Masks > set (`| (1<>k)&1`) > individual bits; shift-and-mask extracts unsigned fields and the left-then-arithmetic-right > shift pair extracts signed ones. Subtracting 1 borrows through the trailing zeros, > which yields the whole `x & (x - 1)` family, and popcount is a loop per set bit > or five parallel adds. C's logical operators `&& || !` are different: they collapse > operands to true/false, return $0$ or $1$, and short-circuit — confusing them with > the bitwise operators is a classic bug. This closes the foundations: from bits and bytes, through integer and floating-point encodings, to the logical algebra over the bits themselves. The next module builds on these representations to study how a processor actually executes instructions. [^tricks]: **Bryant & O'Hallaron**, _CS:APP_, §2.1.7–2.1.9 — Bit-Level and Logical Operations in C: masking idioms, the bitwise/logical distinction, short-circuit evaluation, and bit-manipulation puzzles. [^pop]: **Bryant & O'Hallaron**, _CS:APP_, §2.1 bit-level puzzles (the `bitCount` problem) — counting set bits with masked parallel additions in lanes of doubling width. [^swar]: The SWAR ("SIMD within a register") technique and the zero-byte-detection idiom used by fast `strlen` implementations are collected in **Anderson**'s widely cited "Bit Twiddling Hacks" (Stanford, ~2005) and in **Warren**, _Hacker's Delight_ (2nd ed., 2013), chs. 5–6, the standard references for word-parallel bit manipulation.