News for hackers. Stuff that matters.

A comment on Counting set bits in an interesting way.

Re:Counting set bits in an interesting way by OskarS on Saturday April 30, 2022 @08:32AM (#31215550)
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

[ Parent | on HN ]
Re:Counting set bits in an interesting way by de_huit on Saturday April 30, 2022 @10:24AM (#31216289)
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; 
  }
[ Parent | on HN ]
Re:Counting set bits in an interesting way by omegalulw on Saturday April 30, 2022 @08:56AM (#31215691)
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.
[ Parent | on HN ]
Re:Counting set bits in an interesting way by a_e_k on Saturday April 30, 2022 @01:46PM (#31217754)
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
[ Parent | on HN ]
Re:Counting set bits in an interesting way by Genbox on Saturday April 30, 2022 @09:31AM (#31215939)
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

[ Parent | on HN ]
Re:Counting set bits in an interesting way by mhh__ on Saturday April 30, 2022 @12:28PM (#31217163)
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.
[ Parent | on HN ]
Re:Counting set bits in an interesting way by tikhonj on Saturday April 30, 2022 @12:36PM (#31217219)
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.
[ Parent | on HN ]
Re:Counting set bits in an interesting way by mhh__ on Saturday April 30, 2022 @12:43PM (#31217274)
You should be explicit, but equally profile before worrying about this stuff.
[ Parent | on HN ]
Re:Counting set bits in an interesting way by ycombobreaker on Saturday April 30, 2022 @01:15PM (#31217496)
Purely from a maintenance perspective I would rather somebody use popcnt instructions (if available) over hand-rolling a bit counting algorithm.
[ Parent | on HN ]
Re:Counting set bits in an interesting way by tialaramex on Saturday April 30, 2022 @02:49PM (#31218231)
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.

[ Parent | on HN ]
Re:Counting set bits in an interesting way by tikhonj on Sunday May 01, 2022 @01:32AM (#31222467)
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.
[ Parent | on HN ]