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.<p>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.
I'm quite fond of this classic for popcount [1]:<p><pre><code> int popcnt(unsigned int n) {
int p = 0;
while (n) {
p++;
n &= n-1;
}
return p;
}
</code></pre>
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?<p>[1]: <a href="https://godbolt.org/z/b9rK3sYah" rel="nofollow">https://godbolt.org/z/b9rK3sYah</a>
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.<p>So this bit of x, if set, contributes (1<<i) - (1<<(i-1) + 1<<(i-2) + ... + 1<<0) = 1 to diff altogether.
There is a chapter by Hank Warren all about popcount in the Beautiful Code book, <a href="https://www.oreilly.com/library/view/beautiful-code/9780596510046/" rel="nofollow">https://www.oreilly.com/library/view/beautiful-code/97805965...</a> and there is much more along similar lines in Warren’s book Hacker’s Delight <a href="https://en.m.wikipedia.org/wiki/Hacker's_Delight" rel="nofollow">https://en.m.wikipedia.org/wiki/Hacker's_Delight</a><p>My favourite use of popcount is for packing sparse vectors.
; <a href="http://forum.6502.org/viewtopic.php?t=1206" rel="nofollow">http://forum.6502.org/viewtopic.php?t=1206</a><p><pre><code> 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</code></pre>
> while (x)<p>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:<p>> while (x >= 1)<p>Yeah, it's more code, but it's more readable too.