Glossary

What is SWAR (broadword computing)?

SWAR, "SIMD within a register", treats one 64-bit integer as eight bytes or sixteen 4-bit fields and works on all of them with a few plain adds, shifts and masks. Knuth calls it broadword computing and devotes much of Volume 4A's §7.1.3 to it.

Taught in TAOCP 7.1.3 Bitwise Tricks and Techniques (part 1), TAOCP 7.1.3 Bitwise Tricks and Techniques (part 2)

The classic example: popcount

Counting the 1 bits in a word (sideways addition) without a loop: add adjacent bits in pairs, then adjacent pairs in 4-bit fields, then bytes, using masks like 0x5555... and 0x3333... so the partial sums never overflow into each other. A final multiply gathers the byte sums into the top byte. Six or so instructions replace a 64-step loop.

What else it does

Finding the lowest or highest set bit, testing whether any byte of a word is zero (how fast strlen works), reversing bits, packing and unpacking fields, and branch-free comparisons. Part 2 of §7.1.3 goes further, into broadword algorithms and their lower bounds. Many of these tricks now exist as single CPU instructions, but the reasoning carries over to every place you pack data tightly.

Questions

Is SWAR still useful with real SIMD instructions?

Yes. It needs no special instructions, works in any language with 64-bit integers, and the same ideas apply inside SIMD lanes.