31–38 of 38 posts
If you're into this sort of thing and like print books, "Hacker's Delight" by Henry S. Warren, Jr. is great.
And by small, I mean writing code to fit on a credit card, transit ticket, or SIM card. (Yes <2KB ROM budgets still exist.)
Earlier quoted context omitted.
Indeed it's better to use intrinsics in new code rather than rely on compiler magic https://godbolt.org/z/n3z8nz Portability is an issue though, that works on GCC/Clang but you need a different intrinsic for MSVC
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?
Earlier quoted context omitted.
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.
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.
Earlier quoted context omitted.
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.
Indeed it's better to use intrinsics in new code rather than rely on compiler magic https://godbolt.org/z/n3z8nz Portability is an issue though, that works on GCC/Clang but you need a different intrinsic for MSVC
popcnt(unsigned int):
xor eax, eax
popcnt eax, edi
retEarlier quoted context omitted.
Indeed it's better to use intrinsics in new code rather than rely on compiler magic https://godbolt.org/z/n3z8nz Portability is an issue though, that works on GCC/Clang but you need a different intrinsic for MSVC
Odd that GCC is emitting an xor eax, eax before popcount (in both the intrinsic and pattern cases!): popcnt(unsigned int): xor eax, eax popcnt eax, edi ret
Earlier quoted context omitted.
Odd that GCC is emitting an xor eax, eax before popcount (in both the intrinsic and pattern cases!): popcnt(unsigned int): xor eax, eax popcnt eax, edi ret
It's a workaround for a bug in Intel CPUs: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62011
Earlier quoted context omitted.
Indeed it's better to use intrinsics in new code rather than rely on compiler magic https://godbolt.org/z/n3z8nz Portability is an issue though, that works on GCC/Clang but you need a different intrinsic for MSVC
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?
C++98 gave us std::bitset(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.
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v ^ mask) - mask;