12 ms·

I used to use "implement popcount" as an interview question (for c programmers), I'm not super convinced that it was a good question, although it definitely tel

by pacaro 7y ago

I used to use "implement popcount" as an interview question (for c programmers), I'm not super convinced that it was a good question, although it definitely tells you quite quickly how comfortable a candidate is with bit manipulation. There are three or four reasonable ways to implement it in c, including one weird trick, but which is most efficient tends to be very CPU dependent (at the time I worked on a project that targeted four or five esoteric CPUs so I had the luxury of being able to verify this)

ajxs 7y ago
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]
castratikron 7y ago
I remember in one interview I was asked to write a function that returns true iff x is a power of two, so I wrote return 1 == __builtin_popcount(x). They liked that.
- saagarjha 7y ago
  Another quick way that doesn’t rely on builtins is x && !(x & (x - 1)).
  - tromp 7y ago
    I'd first ask the interviewer whether they're ok with a function is_zero_or_two_power...
    - mkl 7y ago
      Isn't that what the "x &&" is for? For x = 0, (x - 1) is 0xffffffff, x & (x-1) is 0, !(x & (x-1)) is 1, and x && !(x & (x-1)) is 0.
      - tromp 7y ago
        Yes, that's exactly what it's for. The answer I hope for is that they don't care about the case of x==0, so that I can leave out the "x &&" part, leaving the noticeably simpler answer (x & x-1) == 0
- deleted 7y ago
  [deleted]
- nwallin 7y ago
  I did the same thing! But they didn't like it. So I wrote the naivest possible popcount and returned 1 == naive_bitcount(n). They didn't like that. I explained to them that the compiler will optimize or the loop so this will be fast and that they should check it on godbolt. (did I mention that I was coding on the white board?) There's a loop in the source code, but there isn't a loop in the machine code, and it's like three instructions. They didn't like that either, so I worked out the n & (n-1) method from first principals. I didn't do it optimally, there was some redundancy in my code, which the interviewer smugly explained to me. I can't remember if I told him "that's nice, but it's still an extra instruction compared to the trivial, obvious, easy to maintain method I showed you ten minutes ago." I'm pretty sure I didn't, too afraid to make a bad impression. I didn't get the job. In hindsight, I'm glad I didn't. Those guys are dicks.
collyw 7y ago
Why? Its the sort of thing that is used infrequently and you can look it up online. From what I remember the quickest way to do it would be with a lookup hash.
- pacaro 7y ago
  I agree that it's a relatively low signal question, its basically a fizzbuzz for bit twiddling. That being said "Its the sort of thing that is used infrequently and you can look it up online" pretty much describes interview coding questions in general I was definitely just using it as a warm-up/screener question. At the time other popular questions were: • Implement malloc • Pack this nested data structure into contiguous memory • Implement a splay tree Those weren't warm-up questions
bogomipz 7y ago
>"There are three or four reasonable ways to implement it in c, including one weird trick,..." Might you or anyone else have any links or resources you could share on these three or four ways?
- eesmith 7y ago
  Several have already been posted/mentioned. There's also https://en.wikipedia.org/wiki/Hamming_weight https://en.wikipedia.org/wiki/Hamming_weight with a few implementations.

by pacaro 7y ago

ajxs 7y ago

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]

castratikron 7y ago

I remember in one interview I was asked to write a function that returns true iff x is a power of two, so I wrote return 1 == __builtin_popcount(x). They liked that.

saagarjha 7y ago
Another quick way that doesn’t rely on builtins is x && !(x & (x - 1)).
- tromp 7y ago
  I'd first ask the interviewer whether they're ok with a function is_zero_or_two_power...
  - mkl 7y ago
    Isn't that what the "x &&" is for? For x = 0, (x - 1) is 0xffffffff, x & (x-1) is 0, !(x & (x-1)) is 1, and x && !(x & (x-1)) is 0.
    - tromp 7y ago
      Yes, that's exactly what it's for. The answer I hope for is that they don't care about the case of x==0, so that I can leave out the "x &&" part, leaving the noticeably simpler answer (x & x-1) == 0
deleted 7y ago
[deleted]
nwallin 7y ago
I did the same thing! But they didn't like it. So I wrote the naivest possible popcount and returned 1 == naive_bitcount(n). They didn't like that. I explained to them that the compiler will optimize or the loop so this will be fast and that they should check it on godbolt. (did I mention that I was coding on the white board?) There's a loop in the source code, but there isn't a loop in the machine code, and it's like three instructions. They didn't like that either, so I worked out the n & (n-1) method from first principals. I didn't do it optimally, there was some redundancy in my code, which the interviewer smugly explained to me. I can't remember if I told him "that's nice, but it's still an extra instruction compared to the trivial, obvious, easy to maintain method I showed you ten minutes ago." I'm pretty sure I didn't, too afraid to make a bad impression. I didn't get the job. In hindsight, I'm glad I didn't. Those guys are dicks.

collyw 7y ago

Why? Its the sort of thing that is used infrequently and you can look it up online. From what I remember the quickest way to do it would be with a lookup hash.

pacaro 7y ago
I agree that it's a relatively low signal question, its basically a fizzbuzz for bit twiddling. That being said "Its the sort of thing that is used infrequently and you can look it up online" pretty much describes interview coding questions in general I was definitely just using it as a warm-up/screener question. At the time other popular questions were: • Implement malloc • Pack this nested data structure into contiguous memory • Implement a splay tree Those weren't warm-up questions

bogomipz 7y ago

>"There are three or four reasonable ways to implement it in c, including one weird trick,..." Might you or anyone else have any links or resources you could share on these three or four ways?

eesmith 7y ago
Several have already been posted/mentioned. There's also https://en.wikipedia.org/wiki/Hamming_weight https://en.wikipedia.org/wiki/Hamming_weight with a few implementations.