Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Counting set bits in an interesting way

robalni.org

Post reply on HN
Print view View original

1–10 of 34 posts

Re: Counting set bits in an interesting way

#2

Post by tromp »

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.

Re: Counting set bits in an interesting way

#3

Post by goldenkey »

tromp wrote: post #2

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

Re: Counting set bits in an interesting way

#4

Post by OskarS »

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

Re: Counting set bits in an interesting way

#5

Post by omegalulw »

OskarS wrote: post #4

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:…

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.

Re: Counting set bits in an interesting way

#7

Post by Genbox »

OskarS wrote: post #4

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:…

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

Re: Counting set bits in an interesting way

#8

Post by fanf2 »

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.

Re: Counting set bits in an interesting way

#9

Post by de_huit »

OskarS wrote: post #4

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:…

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; 
  }

Re: Counting set bits in an interesting way

#10

Post by le-mark »

fanf2 wrote: post #8

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?
Post reply on HN