4 ms·
I had this as an interview question years ago. I just used a table lookup. It's not compact, but it is fast.
by inetsee 4y ago
I had this as an interview question years ago. I just used a table lookup. It's not compact, but it is fast.
- klyrs 4y agoI'm picturing a naive lookup table solution for a 32-bit popcount, and wondering if there are any text editors that could handle the source gracefully.
- mark-r 4y agoYou can format the source so any editor can handle it. But a 32-bit table is clearly going to be huge. Better to break it into two 16-bit or four 8-bit pieces and add the counts together.
- klyrs 4y agoOf course you can do the not-naive thing to make your editor happy. There's lots of reasons to do the not-naive thing, including but not limited to binary bloat and startup time. Doesn't really answer the question though, does it.
- mark-r 4y agoTable lookups aren't fast if the table isn't in cache. A modern processor can do a lot of instructions in the time it takes to do a cold memory access.
- icedchai 4y agoThis was a Google phone screen question about 10 years ago. Using a lookup table for each byte was key.