This kind of hacks is a major part of how we made Scala.js' 64-bit integers fast (the fastest known implementation of 64-bit integers on JavaScript). See [1] for the implementation, and [2] at section 4.4 for the long explanation with benchmarks and the other tricks we use.
My favorite thing about these is how they come full circle - programmers find convoluted ways to outsmart the compiler in some primitive operation, but then CPU manufacturers add dedicated instructions for those operations, and eventually the compilers outsmart the programmer by deleting their smartass method and emitting a single instruction instead
This of course refers to the POPCNT instruction, that is still quite tricky to get compilers to generate reliably, and which RISC-V specifications and all implementations to date mysteriously lack.
Compilers failing to generate POPCNT cause sometimes 10x slowdowns in key operations.
Any idea why this hasn't been addressed in the C standard? Like C21 could say "math.h shall have a popcnt() function with these semantics", and then the compiler treats that like the intrinsic?
The difficult part is not expressing it. Rather, it is persuading the compiler that the target implements the instruction. gcc and clang have to be convinced they are generating code for an amd64 chip manufactured since 2002 (for which "-mpopcnt" usually works). Common Linux distributions don't turn on any such flags. MSVC offers no way to persuade it, but it will issue the instruction anyway if you use its intrinsic, _popcntN(x), where N is 16, 32, or 64. Shipping Microsoft code doesn't; it is all supposed to work on the oldest amd64 chips ever made.
C++98 gave us std::bitset<N>(x).count(). With C++20 we have std::popcount(x). But getting the compiler to produce the instruction reliably and portably is no easier than before.
At my last job interview I had to implement popcount and explain how to optimise it (amongst other things).
I was able to jot down a naïve implementation and the obvious optimisation based on a lookup tables. I only vaguely remembered the Bit Twiddling treatment of the subject but, with a bit of nudging from the interviewer, I managed to implement and explain the variant that runs in O(set bits) (“Brian Kernighan's way”). I got the job.
Now, it’s fashionable to deride this this kind of code interview as unrealistic and unhelpful. But in my first week on the job, by sheer coincidence, I had to use the function. Obviously there are existing, efficient implementations, including intrinsics. But knowing how to derive an efficient implementation certainly didn’t harm. My job has since evolved into different responsibilities but low-level algorithmic knowledge is still important. I’m not sure testing for it in job interviews is generally a good idea, and designing good job interviews is certainly a big topic. But in my particular case it happened to be a relevant, fair test of my abilities.
I mean, it wouldn't hurt to know how to do all of this, plus all the data structures & algorithms stuff, plus all major and minor details about your language and environment of choice, plus anything else that someone deems important, but realistically most of us need a job before you can learn all of that. Even if you do learn it all, people tend to lose knowledge they don't use, so it may have an expiration date depending on how good your brain is. New technologies and advancements can also introduce more knowledge that becomes required to know for interviews. The pool of knowledge for interview questions might continue to grow until you'd have to study for a year or more to have a high chance of passing it.
> but realistically most of us need a job before you can learn all of that
The interview was for a senior position.
> Even if you do learn it all, people tend to lose knowledge they don't use
Let me emphasise that my interview was not a knowledge test (and at any rate I don’t study for interviews). I wasn’t expected to know by heart how to implement popcount. The interviewer was trying to see me work. Successfully, I might add. — Another question I got concerned something I had no knowledge of, and I had to derive a solution myself. In fact, I failed to do so, but that didn’t prevent me from getting the job since the interviewer was satisfied with what they observed about my thought process.
I’ve had that question twice in google phone screen interviews, and iirc, the best answer has changed from the hash table thing to just use the hardware instruction.
I don't believe companies want to hire for knowing that popcnt exists. The interviewer should follow up with the hypothetical situation when either the language or the CPU doesn't have the instruction.
Nobody should ask this anyway, this has become the fizzbuzz type of question.
Long before leetcode, I used to ask an "algorithm" question in interviews. I don't remember it exactly, but IIRC it was about determining quickly if a number was 2^n-1 for any n. (Don't shoot me, this was a decade ago.)
There were three broad ways candidates answered it:
1) Hack out a for-loop-style bit count. This was good, because even though it wouldn't be optimized, it demonstrated they could understand the problem and at least conceptualize a solution.
2) Give the "leetcode" best-answer (it was some bitwise math trick). I'd then ask if they'd seen the problem before, and the answer was always yes. This was a mark in their favor—but no better than (1)—and also a signal I needed to ask them a follow-up question that actually made them think.
3) Code a bit, but not quite arrive at a solution. I'd then probe them about their thought process. Not an automatic fail, sometimes our brains just don't walk down the corridors we want them to at a given time, especially during an interview. (One candidate couldn't hold the marker steady because his hands were shaking too much! Poor guy.)
4) Give up and say they had no idea. Obviously the worst case for the interviewee.
The purpose was not to check a candidate's recall and test-taking abilities, but rather to watch them reason through a novel problem, appropriately limited in scope for the interview timeframe. Case (2) served as a great short-circuit to block test-preppers lacking actual experience.
Yeah, it's a stupid question, which is why I was surprised that Google asked it to me twice, separated by a couple of years.
What's funny is that 15 years later, I actually had a use for popcnt, put it together with something that seemed expensive at the time, and wound up with a C program that exhaustively searched a problem space in .12 sec. On a single core, in a vm, on a laptop. So much for me trying GPU programming on that one. (as in , feckit, there aren't that many possibilities, we'll just count them all)
These are typically seen as tricks for embedded programming. But they have (at least) another useful application.
Years ago I was messing around with SAT-based bounded model checking of C programs that I was crafting. Many of these tricks allow you to remove branches/loops from your program, which is great because you end up with a smaller SAT formula, which (usually) can be solved faster.
This list is super-great, except: all modern targets[0] (and many non-modern, including Alpha, Cray, CDC, Stretch) have the POPCOUNT instruction, which does a key operation underlying a large portion of the target operations much faster than presented. It provides an order-of-magnitude speedup in numerous algorithms. The list should have a comprehensive treatment.
At the moment, the only ISO Standard way to say "popcount" is in C++, with e.g.
std::bitset<64>(x).count()
But even this is insufficient on MSVC, which targets pre-2002 arm64, which lacked it; and on gcc and clang on amd64, similarly, absent a -fpopcnt or -march=native or related option (which there are numerous other reasons to use).
Given -march=native or =core2 or various other means, optimizers will happily rewrite the Kernighan loop into a straight-up POPCNT instruction. Anyway, all compilers provide it as a non-standard, therefore variously-spelled, intrinsic, but (except on MSVC) only actually produce it if the "-march=" or related commad-line option enables that.
Historically, it is common for instruction sets to start out lacking the instruction, and then getting it in subsequent releases because of customer demand. Also historically, a key such customer has frequently been the US NSA. Thus, initial and64, alpha, POWER, and SPARC lacked it, but soon got it. x86 ("ia32") is perhaps the principal laggard. When a feature is added, at great expense, to a subsequent ISA revision, that says a lot for its importance.
[0] All except RISC-V, to date. Some would say this makes RISC-V non-modern. It appears in the (still) unratified B extension, which (therefore) nobody implements.
I once had to count the number of set bits (the Hamming weight) for an assignment. It had to be done in under 40 bitwise ops, without loops and with constants of up to 8 bits. The naive approach took way too many ops! I was stumped until I found the linked page, in particular 'Counting bits set, in parallel'[1]. Parallelism at the bit level?! That is when I realized low level programming was completely badass.
Having written my fair share of bit-twiddling hacks in low-level code, my takeaway is that because the hack code doesn't resemble what it actually does, it's all too easy to create bugs. Unit testing the living daylights out of any bit-twiddling code path is a must.
Also helpful: being able to represent integer types with binary. Since I'm not a genius and I write code to be maintained by other not-geniuses, `mask = 0b_1010_1010` is clearer than `mask = 0xAA`.
Another simple bit-twiddling-hack (it has a proper name which I unfortunately forgot) is SIMD without SIMD instructions by masking out the top-level bits (which are essentially the carry-flags), e.g. doing eight 7-bit additions at once:
uint64_t a = ((a0 & 0x7F) | ((a1 & 0x7F)<<8) ...;
uint64_t b = ((b0 & 0x7F) | ((b1 & 0x7F)<<8) ...;
uint64_t c = (a + b) & 0x7F7F7F7F7F7F7F7F;
A trick I used to get the mask of least significant set bit in a bit mask: `flag = bitmask & (-bitmask)`. Works with two's complement numbers only of course. (and modern architectures have a dedicated command for this)
[1] https://github.com/scala-js/scala-js/blob/v1.3.1/linker-priv...
[2] https://lampwww.epfl.ch/~doeraene/thesis/doeraene-thesis-201...