5 ms·

Can you share the different ways it was done? Everything in your post sounds quite interesting.

• dalke 7y ago
  I can. About 10 years ago I put together a series of blog posts on the topic. It's even referenced from the linked-to article. Most of the algorithms are described at http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html http://www.dalkescientific.com/writings/diary/archive/2008/0... . http://dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html http://dalkescientific.com/writings/diary/archive/2011/11/02... has a link to http://dalkescientific.com/writings/diary/popcnt.cpp http://dalkescientific.com/writings/diary/popcnt.cpp containing implementations in a benchmark. That code only goes up to the POPCNT instruction. Faster implementations use AVX2 instruction set to implement the Harley-Seal algorithm, and there's VPOPCNTDQ in AVX 512 which does 512 bits at a time. Table of my preprint at https://chemrxiv.org/articles/The_Chemfp_Project/7877846 https://chemrxiv.org/articles/The_Chemfp_Project/7877846 shows the comparison of the most reasonable algorithms (for my definition of 'reasonable') on relatively modern hardware. For my case, the AVX2 implementation, fully optimized, is 11x faster than a lookup table and 30% faster than AVX2. Note that my case handles (typically) multiword popcounts containing 512-2048 bits. Some of the implementations sum the popcount of each word, a few of them use techniques to work on multiple words at a time. (For example, the Gillies-Miller method for "sideways addition" - an old term for popcount - dates from the 1950s. https://archive.org/details/programsforelect00wilk/page/190 https://archive.org/details/programsforelect00wilk/page/190 . )
• pacaro 7y ago
  Sure! The simplest is a loop that increments a counter if the least significant bit is 1 and right shifts the word by 1 each iteration. Bonus points for early termination One weird trick is to consider (w & (w - 1)) which unsets the lowest set bit The other major approach is to use lookup tables for some segment of the word, usually nybble or byte, if this is done on a divide and conquer approach you can short-circuit parts of the word that are zero [Edit] dalke's answer is much more detailed! I last thought about this stuff in about 2001 or so
  • eru 7y ago
    Btw, depending on application, sometimes you don't want early termination. Eg for some cryptographic applications you don't want to leak information about what data you are working on in the runtime of your algorithm. Another (more far-fetched?) scenario might come up with either branch prediction and CPU pipelining, or your compiler's optimizer recognising the simple loop but not the one that has early abort.
    • pacaro 7y ago
      Yeah, creating constant time code is its own challenge, if a candidate were to bring that up it could take the interview down a very different path
    • a1369209993 7y ago
      > either branch prediction and CPU pipelining Not that far-fetched; the non-early-aborting loop can be branch-predicted perfectly by a smart enough CPU.
• missblit 7y ago
  See also: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive https://graphics.stanford.edu/~seander/bithacks.html#CountBi...
• deleted 7y ago
  [deleted]