Counting set bits in an interesting way | Hacker News Reader

Counting set bits in an interesting way

robalni.org

63 pointsrobalni33 comments

For production code as opposed to exams of job interviews, it’s usually better to use hardware implementation. All modern CPUs have instructions for that, popcnt on Intel/AMD, vcnt.8 on ARM Neon.

Many languages have standard library functions, or hardware intrinsics, to emit these instructions: std::popcount in C++/20, _popcnt32 and _popcnt64 intrinsics for Intel/AMD, __builtin_popcount in gcc/clang, BitOperations.PopCount in C#, etc.

Compilers can often recognize idiomatic implementations of intrinsics in languages where it is not part of the standard library, doing the appropriate substitution at compile-time. This has the advantage of being highly portable to environments that either lack the intrinsics or don't recognize the idioms without conditional compilation. This typically requires a little experimentation with Godbolt or similar to identify idiomatic C expressions of intrinsics that are consistently recognized across most/all popular compilers.

That said, the reduction in diversity of target platforms, at least on the server side, combined with convergence of language extensions support in compilers has made this less useful than it used to be. I mostly just used builtins and intrinsics these days.

>All modern CPUs have instructions for that

Not in the embedded space. Here's the architectures supported by gcc. I suspect most of them do not have popcount equivalent instructions. I've used quite a few of them and the only places I expect hardware support are on Intel and ARM. Rarely does another arch have it.

https://gcc.gnu.org/backends.html

I'm quite fond of this classic for popcount [1]:

    int popcnt(unsigned int n) {
        int p = 0;
    
        while (n) {
            p++;
            n &= n-1;
        }
    
        return p;
    }

But it has a branch in it, so I don't know if it's competitive with the "simple" version of just counting the ones or this version, even though the loop should run fewer iterations. Obviously the real answer is to just use the compiler intrinsics for this, but what fun is that?

[1]: https://godbolt.org/z/b9rK3sYah

The version from Hacker's delight is fun and does not branch:

  int popcount32(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F);
    return (i * 0x01010101) >> 24; 
  }

For those wondering how this works, n & n-1 zeros out the least significant 1. Simply by doing this repeatedly you count the number of 1s.

Right. And the reason that zeroes out the least significant bit is because subtracting one just borrows up to it. E.g., for n = 464:

    n       = 464d 111010000b
    n-1     = 463d 111001111b
    n&(n-1) = 448d 111000000b

The builtin POPCNT that came with Intel's SSE4 (SSE4a for AMD) is much faster. However, at a certain point, using AVX2 (and AVX-512 if present) is actually faster yet [1] - at least for 512 byte inputs or larger.

[1]: https://github.com/WojciechMula/sse-popcount

If the compiler is allowed to do loop idiom recognition and scalar optimization, writing the dumb thing rather than reaching for an intrinsic can have the same result as the intrinsic.

That's true, but in any scenario where it mattered, I'd hate to rely on it. Compilers have the idiom recognition pass as a sort of hack for speeding up existing codebases but it's ultimately just a heuristic. When I write code, I would much prefer to be explicit about things like that.

You should be explicit, but equally profile before worrying about this stuff.

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.

The way I see it as working, is that the i'th bit in x is initially added to the i'th bit in diff, and subsequently subtracted from the (i-1)th, the (i-2)th, ... the 0th bit of diff.

So this bit of x, if set, contributes (1<<i) - (1<<(i-1) + 1<<(i-2) + ... + 1<<0) = 1 to diff altogether.

Nice analysis, it's basically just an alternating series that uses the inclusion exclusion principle.

https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_pr...

There is a chapter by Hank Warren all about popcount in the Beautiful Code book, https://www.oreilly.com/library/view/beautiful-code/97805965... and there is much more along similar lines in Warren’s book Hacker’s Delight https://en.m.wikipedia.org/wiki/Hacker's_Delight

My favourite use of popcount is for packing sparse vectors.

Interesting, can you describe a sparse vector and how it’s packed using pop count?

https://news.ycombinator.com/item?id=10329598:

"You can use popcount() to implement a sparse array of length N containing M < N members using bitmap of length N and a packed vector of M elements. A member i is present in the array if bit i is set, so M == popcount(bitmap). The index of member i in the packed vector is the popcount of the bits preceding i."

FWIW: These kind of sparse array tricks have been around forever:

https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html

The original idea for that patch didn't come from philip bagwell's paper, but from some code from the late 80's i saw at IBM.

Thus, i suspect this kind of thing has been around forever

; 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

> 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.

Speaking of the while head, after posting this I realized that there is an optimization you can do by moving the bitshift into the while head, like this:

while (x >>= 1)

This makes gcc compile the code to one instruction less per iteration because it can use the status flags generated by the bitshift to determine whether to jump. Now the loop will only be 3 instructions long and the entire function 8 instructions. https://godbolt.org/z/fna8de367

whoosh

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.

Which of the 2 versions is more readable is a matter of personal opinion.

Many people consider that the most readable programs are those in which nothing is written in a longer more complex form, if it can be written in a shorter simpler form.

The implicit conversion of a value of any type to a Boolean value is not something invented by C. This was first used in LISP I (1960), then in many other programming languages.

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

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.

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.

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.

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.

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

Reply on news.ycombinator.com