[HN Gopher] Counting set bits in an interesting way
___________________________________________________________________
Counting set bits in an interesting way
Author : robalni
Score : 56 points
Date : 2022-04-28 16:42 UTC (2 days ago)
(HTM) web link (www.robalni.org)
(TXT) w3m dump (www.robalni.org)
| tromp wrote:
| 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.
| goldenkey wrote:
| 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...
| fanf2 wrote:
| 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.
| le-mark wrote:
| Interesting, can you describe a sparse vector and how it's
| packed using pop count?
| Someone wrote:
| 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_
| Const-me wrote:
| 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.
| jandrewrogers wrote:
| 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.
| ChrisLomont wrote:
| >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
| mmphosis wrote:
| ; 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
| mark-r wrote:
| You could remove one branch by doing add 0 with carry instead
| of the increment.
| mmphosis wrote:
| ; 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
| svnpenn wrote:
| > 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.
| robalni wrote:
| 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
| svnpenn wrote:
| whoosh
| adrian_b wrote:
| 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.
| jandrewrogers wrote:
| 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.
| OskarS wrote:
| 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
| mhh__ wrote:
| 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.
| tikhonj wrote:
| 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.
| mhh__ wrote:
| You should be explicit, but equally profile before worrying
| about this stuff.
| ycombobreaker wrote:
| Purely from a maintenance perspective I would rather
| somebody use popcnt instructions (if available) over
| hand-rolling a bit counting algorithm.
| tialaramex wrote:
| 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.
| Genbox wrote:
| 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
| omegalulw wrote:
| 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.
| a_e_k wrote:
| 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
| de_huit wrote:
| 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; }
| inetsee wrote:
| I had this as an interview question years ago. I just used a
| table lookup. It's not compact, but it is fast.
| klyrs wrote:
| 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.
| mark-r wrote:
| 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.
| klyrs wrote:
| 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.
| mark-r wrote:
| 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.
| icedchai wrote:
| This was a Google phone screen question about 10 years ago.
| Using a lookup table for each byte was key.
___________________________________________________________________
(page generated 2022-04-30 23:01 UTC)