Pop goes the...population count?
19 points by LesleyLai
19 points by LesleyLai
The general name for this is idiom recognition. LLVM does similar things for count leading/trailimg zeroes. https://llvm.org/doxygen/LoopIdiomRecognize_8cpp.html
A simpler kind of idiom recognition turns combinations of shifts into rotate instructions, handy for random numbers and cryptography.
If you’re ever looking for popcount in TAOCP, Knuth peculiarly calls it “sideways add” instead.
I like popcount-packed arrays, which I use to great advantage in my qp-trie. I got the idea from Bagwell’s HAMT.
Compilers also tend to recognize byte-swaps — you implement big/little-endian conversion as a bunch of messy and/shift/or expressions, and the compiler replaces it with one byte-swap instruction.
Yeah, there are several data structures that use a bitmap to identify which values exist in a sparse array, then compute the actual array index by counting the number of 1 bits to its left. I’ve seen the HAMT, and also I think there’s a space-efficient hash table that uses the same trick.