21–30 of 34 posts
I had this as an interview question years ago. I just used a table lookup. It's not compact, but it is fast.
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.
Earlier quoted context omitted.
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.
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.
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.Po…
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.
> 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. ht…
Earlier quoted context omitted.
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.
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.
> 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.
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.
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
RTSFor 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.Po…
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.
; 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