3 ms·
There is a chapter by Hank Warren all about popcount in the Beautiful Code book, https://www.oreilly.com/library/view/beautiful-code/9780596510046/ https://www.
by fanf2 5y ago
There is a chapter by Hank Warren all about popcount in the Beautiful Code book, https://www.oreilly.com/library/view/beautiful-code/9780596510046/ https://www.oreilly.com/library/view/beautiful-code/97805965... and there is much more along similar lines in Warren’s book Hacker’s Delight https://en.m.wikipedia.org/wiki/Hacker's_Delight https://en.m.wikipedia.org/wiki/Hacker's_Delight
My favourite use of popcount is for packing sparse vectors.
- le-mark 5y agoInteresting, can you describe a sparse vector and how it’s packed using pop count?
- Someone 5y agohttps://news.ycombinator.com/item?id=10329598 https://news.ycombinator.com/item?id=10329598: "You can use popcount() to implement a sparse array of length N containing M < N members using bitmap of length N and a packed vector of M elements. A member i is present in the array if bit i is set, so M == popcount(bitmap). The index of member i in the packed vector is the popcount of the bits preceding i." FWIW: These kind of sparse array tricks have been around forever: https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html The original idea for that patch didn't come from philip bagwell's paper, but from some code from the late 80's i saw at IBM. Thus, i suspect this kind of thing has been around forever