Counting set bits in an interesting way • Hacker News Board

Re: Counting set bits in an interesting way

#31

Post by jandrewrogers » Sat, Apr 30, 2022, 8:20 PM UTC

svnpenn wrote: post #17

> while (x) I never realized how much I hate this style of code until I started using Go. Go only allows Boolean conditions, so you have to do this: > while (x >= 1) Yeah, it's more code, but it's more readable too.

These are not guaranteed to be equivalent expressions even for integer types. It improperly conflates boolean casts (the first case) and boolean comparisons (the second case). In languages like C++ this is an important and commonly used semantic distinction that enables cleaner abstractions because the latter case is making assumptions about the type implementation.

Both styles are used but they have distinct meanings in context.

Re: Counting set bits in an interesting way

#32

Post by mmphosis » Sat, Apr 30, 2022, 8:53 PM UTC

mark-r wrote: post #30

mmphosis wrote: post #28

; http://forum.6502.org/viewtopic.php?t=1206 LDX #$00 ; clear bit count loop ASL ; shift a bit BCC skip ; did one shift out? INX ; add one to count skip BNE loop ; repeat till zero RTS

You could remove one branch by doing add 0 with carry instead of the increment.

; yes, A becomes the counter, and shift a zero page byte

  byte  EQU $EB
        STA byte
        LDA #$00
        CLC
  loop
        ADC #$00
        LSR byte
        BNE loop
        ADC #$00
        RTS

Re: Counting set bits in an interesting way

#33

Post by icedchai » Sat, Apr 30, 2022, 9:15 PM UTC

inetsee wrote: post #6

I had this as an interview question years ago. I just used a table lookup. It's not compact, but it is fast.

This was a Google phone screen question about 10 years ago. Using a lookup table for each byte was key.

Re: Counting set bits in an interesting way

#34

Post by tikhonj » Sun, May 01, 2022, 5:32 AM UTC

tialaramex wrote: post #23

ycombobreaker wrote: post #16

Earlier quoted context omitted.

Purely from a maintenance perspective I would rather somebody use popcnt instructions (if available) over hand-rolling a bit counting algorithm.

Exactly. Write your intention first. Only write something else if you had a measurable performance problem and the change fixed it. If you didn't measure, that wasn't a performance improvement, it just was wanking. Let the compiler, and library writers take care of most of the work of translating your intention into good runtime performance and only intervene when they don't get the job done.

The point is that writing "__builtin_popcount" makes your intentions clearer than implementing popcount as a loop. The guaranteed performance is downstream of the clarity: since the code is more explicit, the compiler doesn't have to rely on heuristics to guess that you want popcount, so it will always do the right thing.