Counting set bits in an interesting way

Re:Counting set bits in an interesting way by fanf2 on Saturday April 30, 2022 @10:17AM (#31216238)

There is a chapter by Hank Warren all about popcount in the Beautiful Code book, 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

My favourite use of popcount is for packing sparse vectors.

[ Parent | on HN ]

Re:Counting set bits in an interesting way by le-mark on Saturday April 30, 2022 @11:31AM (#31216772)

Interesting, can you describe a sparse vector and how it’s packed using pop count?

[ Parent | on HN ]

Re:Counting set bits in an interesting way by Someone on Saturday April 30, 2022 @12:55PM (#31217361)

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

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

[ Parent | on HN ]