4 ms·

In the past I would use “Five Essential Phone-Screen Questions”. The last question is on bit twiddling. A sample question might be “count how many bits in this

In the past I would use “Five Essential Phone-Screen Questions”. The last question is on bit twiddling. A sample question might be “count how many bits in this byte are 1”. I don’t know if it is fair to assume that all developers know this stuff. When interviewing engineers who claimed experience with anything embedded (MCU programming or field busses like CAN or modbus), I don’t know how it would be possible to program anything at the lowest layers without but shifting. But even in an embedded world you spend most of your time writing application logic. Outside of the embedded world you can get away with repenting things without worrying about bits. Particularly in higher level languages it might be more natural to have a strict with several named bools or an array of bools. One language that makes working with bitfields much more pleasant is C#. You can apply a Flags attribute to an enum type. At runtime it represented by an int, so it’s fast. But it also has handy methods for converting to and from a string form that gives names to all the bits that are set. So it’s fairly friendly for logging and debugging. https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions https://sites.google.com/site/steveyegge2/five-essential-pho...

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 ago
  even llvm will translate the popcount intrinsic into the code you want for you! just use it freely.
- Sniffnoy 5y ago
  Man, 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 ago
      Deliberately 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; }
dnautics 5y ago
well these days LL PLs tend have the popcount intrinsic...

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 ago
even llvm will translate the popcount intrinsic into the code you want for you! just use it freely.
Sniffnoy 5y ago
Man, 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 ago
    Deliberately 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; }

dnautics 5y ago

well these days LL PLs tend have the popcount intrinsic...