News for hackers. Stuff that matters.
Re:Counting set bits in an interesting way by inetsee on Saturday April 30, 2022 @09:14AM (#31215841)
I had this as an interview question years ago. I just used a table lookup. It's not compact, but it is fast.
Re:Counting set bits in an interesting way by mark-r on Saturday April 30, 2022 @02:38PM (#31218144)
Table 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.
Re:Counting set bits in an interesting way by klyrs on Saturday April 30, 2022 @02:31PM (#31218082)
I'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.
Re:Counting set bits in an interesting way by mark-r on Saturday April 30, 2022 @02:41PM (#31218167)
You 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.
Re:Counting set bits in an interesting way by klyrs on Saturday April 30, 2022 @03:19PM (#31218455)
Of 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.
Re:Counting set bits in an interesting way by icedchai on Saturday April 30, 2022 @05:15PM (#31219440)
This was a Google phone screen question about 10 years ago. Using a lookup table for each byte was key.