Lecture 3: Bit Hacks

What this lecture covers

This lecture teaches low-level bit manipulation techniques in C: how binary and two's complement representation work, the standard bitwise operators, and a series of idioms built from them. Many tricks (branchless swap, branchless minimum) are presented and then shown to underperform on modern optimizing compilers, which the lecture treats as an important lesson in itself, not a contradiction: knowing the tricks helps you read compiler-generated assembly and apply them when the compiler doesn't.

After watching, you should be able to set, clear, toggle, and extract bit fields in a word; explain why some "clever" bitwise tricks are actually slower than straightforward code on modern hardware due to instruction-level parallelism and branch prediction; and understand how techniques like sparse bit-vector board representations and population count apply to real problems such as N-Queens.

Key ideas

• Two's complement: negative numbers are represented so the all-ones word equals -1, giving the identity -x = ~x + 1, which underlies several other tricks.
• Basic bit idioms: setting, clearing, toggling, extracting, and setting a bit field all use combinations of shift, &, |, ~, and ^ with a constructed mask.
• Branchless swap and minimum: XOR-based swap and comparison-mask-based minimum avoid branches but can be slower than naive code because they remove instruction-level parallelism or because modern compilers already eliminate the branch with a conditional-move instruction.
• Predictable vs. unpredictable branches: a branch that almost always goes the same way is cheap for the hardware to predict; one that is roughly 50/50, like comparing two unsorted array elements during a merge, is expensive on misprediction and a candidate for branchless code.
• Sparse bit-vector board representation: representing an N-Queens board with three bit vectors (columns and both diagonals) instead of a full grid lets queen-placement safety checks become single AND operations.
• Population count (pop count): counting set bits in a word can be done by repeatedly clearing the lowest set bit, by table lookup, by a parallel divide-and-conquer bit trick, or via a hardware instruction, with real performance tradeoffs between them.
• De Bruijn sequences: a cyclic bit sequence containing every possible k-bit substring exactly once, used to compute log2 of a power of two via a multiply and table lookup.

Walkthrough

Binary and two's complement representation (0:01)

The lecture reviews how an unsigned word encodes a value as a sum of powers of two, then introduces two's complement for signed integers, where the leftmost bit is subtracted rather than added. Key facts include that the all-ones word equals -1 and that -x equals the ones' complement of x plus one.

Bitwise operators and basic idioms (7:11)

C's &, |, ^, ~, and shift operators are demonstrated, followed by idioms for setting, clearing, and toggling the k-th bit of a word using a shifted mask, and extracting or setting a bit field using a mask combined with a shift.

Branchless swap and minimum (16:23)

A no-temp swap using three XOR operations is explained via a truth table, then shown to be poor at exploiting instruction-level parallelism because its three steps are sequentially dependent, unlike a temp-variable swap. A branchless minimum trick using XOR and a negated comparison result is derived, then shown to typically lose to compiler-optimized branching code because compilers already generate a conditional-move instruction.

Predictable branches in array merging (25:37)

Using the merge step from merge sort as an example, the lecture classifies each branch in the code as predictable or unpredictable. The comparison between the next elements of the two input arrays is unpredictable (close to 50/50), making it a good candidate for the branchless minimum trick, while the loop-exit checks are predictable and don't need it.

Rounding to a power of two and least-significant-bit tricks (37:52)

The lecture derives a bit trick that rounds a value up to the next power of two by propagating the highest set bit rightward with successive shifts and ORs, then adding one. It also covers computing a mask of the least significant 1 bit using x & -x.

De Bruijn sequences and the log-base-2 trick (43:56)

To find the index of a set bit (log2 of a power of two), the lecture introduces de Bruijn sequences, cyclic bit strings containing every possible substring of a given length exactly once, and shows how multiplying by a de Bruijn constant and looking up the result in a small table yields the bit index. A class demonstration (a card "mind-reading" trick) illustrates the same underlying structure.

N-Queens and bit-vector board representation (59:19)

For the N-Queens problem, solved by row-by-row backtracking, the lecture compares board representations: a full N-squared array, a compact N-byte array (one queen per row), and finally three bit vectors, tracking occupied columns and both diagonals, that let a placement's safety be checked with three AND operations instead of scanning the board.

Population count (1:07:39)

Three approaches to counting set bits are compared: repeatedly clearing the lowest set bit (cost proportional to the number of set bits), table lookup on 8-bit chunks (cost bounded by word size but limited by memory access latency), and a parallel divide-and-conquer bit trick that sums bit-pair counts in registers with cost proportional to log2 of the word length. The lecture notes that most modern hardware has a native pop-count instruction that outperforms all of these, accessible via compiler intrinsics.

Before you watch

• Watch Lectures 1 and 2 first for the course's framing of performance and the general optimization vocabulary used throughout.
• Comfort with binary numbers, hexadecimal notation, and basic C syntax is expected.
• Familiarity with the N-Queens problem and merge sort helps but is not required.

Check your understanding

1. Why can a branchless bit trick sometimes run slower than the equivalent branching code on a modern compiler?
2. What distinguishes a predictable branch from an unpredictable one, and why does that distinction matter for performance?
3. How does the sparse bit-vector representation speed up safety checks in the N-Queens backtracking search?
4. Explain how a de Bruijn sequence and its lookup table are used to compute the index of a set bit.
5. What are the tradeoffs between the three population-count methods described in the lecture?