Boolean Algebra and Bit Manipulation

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, 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.

Read on full words, the four become parallel operations over all $w$ lanes. With $a=0x69=01101001$ and $b=0x55=01010101$:

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 $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.

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.

/* 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); }

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:

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: 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:

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$.

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.

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: $\dots 1\underset{k}{\underbrace{00\dots 0}}$. 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:

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=01101000$: $-x=10011000$, and the AND is $00001000=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, and the standard way to align a size or an address.

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.¹

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.

/* 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).²

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.³ 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.

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 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.

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.