Broad Word Computing

Knuth presents bit-flipping tricks as broad word computing. For me, bit-flipping is something that languages try to hide from programmers. But Knuth begins to code single-instruction-multiple-data (SIMD) using bitwise operators. He shows a few lines which will average two vectors, x and y, each with 8, 8-bit integers (Video 37m45s).

l = 0x0101010101010101;

t = ((x^y) & ~l) >> 1;
z = (x&y) + t;

Then, Knuth used bitwise operators to multiply a 4x4 binary matrix. He had to use the full 64-bits to do it. Larger matricies require even wider words. An 8x8 matrix would require 8^3-bit registers. Yet, the number of instructions remain the same!

The computational effort is being moved from the software instructions into additional memory space and circuitry.