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

11–20 of 34 posts

Re: Counting set bits in an interesting way

#11

Post by mhh__ »

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

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.

Re: Counting set bits in an interesting way

#12

Post by tikhonj »

mhh__ wrote: post #11
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:…

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.

Re: Counting set bits in an interesting way

#13

Post by mhh__ »

tikhonj wrote: post #12
mhh__ wrote: post #11

Earlier quoted context omitted.

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.

Re: Counting set bits in an interesting way

#14

Post by Const-me »

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.

Re: Counting set bits in an interesting way

#15

Post by Someone »

le-mark wrote: post #10
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?

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

"You can use popcount() to implement a sparse array of length N containing M 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

Re: Counting set bits in an interesting way

#16

Post by ycombobreaker »

mhh__ wrote: post #13
tikhonj wrote: post #12

Earlier quoted context omitted.

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.

Re: Counting set bits in an interesting way

#18

Post by robalni »

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.

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

Re: Counting set bits in an interesting way

#19

Post by a_e_k »

omegalulw wrote: post #5
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.

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

Re: Counting set bits in an interesting way

#20

Post by klyrs »

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.

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