3 ms·
Here's an issue I have with that question. > A sample question might be “count how many bits in this byte are 1” Use the Popcnt assembly instruction. > But w
by dragontamer 5y ago
Here's an issue I have with that question.
> A sample question might be “count how many bits in this byte are 1”
Use the Popcnt assembly instruction.
> But what if the popcnt assembly instruction doesn't exist on your platform?
Popcnt exists on POWER9, ARM, x86, NVidia PTX (GPU Assembly), AMD RDNA, AMD CDNA, AMD GCN.
> But no, really this interview is about seeing if you're able to answer the question in a manner that's familiar to the interviewer... and not really how you'd solve the problem in practice.
Fine fine fine. I'll open up my "Art of Computer Programming Volume 4A, Bitwise Tricks" and copy/paste the algorithm specified therein. I don't keep the particulars of how to implement popcount in my brain anymore because its implemented in most CPUs / GPUs these days, AND I can look it up if you happen to be on an uncommon platform in pretty standard bitwise-tricks based programming books.
--------
But really, the interviewer would want to know "You do the weird "(x & 0x5555) + ((x & 0xAAAA) >> 1) (etc. etc.)" routine.
But really, the practical answer (aka: use a single-cycle popcnt instruction available on all mainstream desktop-class CPUs and GPUs I can possibly imagine in today's world) is still the "wrong answer".
---------
I think a better interview question would be: Demonstrate mastery of horizontal SIMD-programming, __such as__ implementing the popcnt instruction out of bitshifts, adds, and "AND" instructions.
Or, demonstrate said parallel programming mastery over any other similar problem (be it lookahead carry addition, or kogge-stone bishop/rook moves in chess, or whatever).
That's what you really are trying to figure out when you ask the question. Anyone can solve "popcnt" or look it up with a quickie search (either on the internet, or reading through a book). But the overall methodology generalizes to many problems in the SIMD-programming space, so its an important skill to have.
But also, its important for the interviewer to demonstrate having this skill to the interviewee. Otherwise, you lose the interviewee. (Skilled individuals want their skills recognized. If you fail to recognize their skill during the interview, they'll seek someone else)
- dnautics 5y agoeven llvm will translate the popcount intrinsic into the code you want for you! just use it freely.
- Sniffnoy 5y agoMan, I wish languages gave us easy access to these sorts of instructions. So many times I've written a loop to count how many times divisible by 2 a number is, when there has to be an instruction for that... yes, notionally I could drop down into assembly, but that would require learning how to do so in the relevant language! Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before.
- dragontamer 5y ago> Out of curiosity, what is this weird way of computing popcount you mention? I haven't seen it before. So lets just do 8-bits at a time, in binary. It makes it clear what's going on. Your 8-bit number is: x = x0 x1 x2 x3 x4 x5 x6 x7 * 0x55 is 01010101 in binary. * 0xAA is 10101010 in binary. * (x & 0x55) is (0 & x0) (1 & x1) (0 & x2) (1 & x3)... * (x & 0xaa) is (1 & x0) (0 & x1) (1 & x2) ... * (x & 0x55) + ((x & 0xaa) >> 1) is: |x0 + x1|,|x2 + x3|,|x4+x5|, |x6+x7|, where |blahblah| is a 2-bit number taking up 2-bits of the 8-bit number. * step2 = (x & 0x55) + ((x & 0xaa) >> 1) * (step2 & 0x33) is now |00| |x2+x3| |00| |x6+x7| * (step2 & 0xcc) is now |x0+x1| |00| |x4+x5| |00| * (step2 & 0x33) + ((step2 & 0xcc) >> 2) is //x0+x1+x2+x3// //x4+x5+x6+x7//, where //blah// is a 4-bit number. You probably can figure out the last step at this point. Take the bottom 4 bits and add them with the top 4 bits. A 2-bit number (such as |x0+x1|) can only take on 3 values: 0, 1, or 2. As such, |x0+x1| will never "carry" outside of the 2-bit space you've allocated for it. Similarly, a 4-bit number (such as //x0+x1+x2+x3//) can only take on 5 values: 0, 1, 2, 3, 4. The 4-bits you've allocated can take on values all the way up to 16, so you also never have to worry about overflow.
- a1369209993 5y agoDeliberately more obviously 'weird' version, from memory: uint64_t x = ...; for(size_t i = 1; i<UINT_BIT ;i*=2) // loop unroll { unsigned m = UINT_MAX / ((1<<i)+1); // constant-fold // divide 2^(2k)-1 by 2^k+1 to get 2^k-1 in each group // 2k-bit group means 2^k-1 sets bottom half x = (x & m) + (x>>i & m); // we can save a AND w/o carry but 1-bit and 2-bit // need 2 ANDs to prevent carry between groups // x = (x + (x>>i)) & m; }
- MarkSweep 5y agoI agree with everything you say. Whether someone gets this question right or wrong does not really tell you anything about whether you should hire them. In my defense, at the time I was asking this question question I was fresh out of college and my company gave no training or guidance on how to interview.
- dragontamer 5y agoOh, don't worry. I'm not necessarily criticizing you in particular (I wasn't part of that interview :-) ). Its just kind of in the abstract sorta thing. If anything, I'm trying to agree with your original post, and just kinda ranting a bit myself on a similar subject.
- Zababa 5y agoYour answer is great, however the questions comes with a disclaimer: > Please understand: what I'm looking for here is a total vacuum in one of these areas. It's OK if they struggle a little and then figure it out. It's OK if they need some minor hints or prompting. I don't mind if they're rusty or slow. What you're looking for is candidates who are utterly clueless, or horribly confused, about the area in question. If you follow this, the way you reply is perfect. Someone using divisions would work too. Someone simply mapping all the values of a byte to the number of bits that are 1 would work too.
- majormajor 5y agoI've never actually had an interviewer reject my solution for not being identical to the one they had in mind. Are you basing this on real experience, or assumption? If I asked you that as a "do they know about bits and bytes at all" question and you said "here's an assembly function that's available everywhere" I'd be like "great, they clearly are more familiar than I am about that space." The closest I've run into has been the interviewer who's like "use any language you like" who then couldn't seem to grasp that `.each` in Ruby is basically the same as `for(x : things)` and kept bugging me about it until I said fuck it and just used Python instead.