6 ms·
I remember in one interview I was asked to write a function that returns true iff x is a power of two, so I wrote return 1 == __builtin_popcount(x). They liked
by castratikron 7y ago
I remember in one interview I was asked to write a function that returns true iff x is a power of two, so I wrote return 1 == __builtin_popcount(x). They liked that.
- saagarjha 7y agoAnother quick way that doesn’t rely on builtins is x && !(x & (x - 1)).
- tromp 7y agoI'd first ask the interviewer whether they're ok with a function is_zero_or_two_power...
- mkl 7y agoIsn't that what the "x &&" is for? For x = 0, (x - 1) is 0xffffffff, x & (x-1) is 0, !(x & (x-1)) is 1, and x && !(x & (x-1)) is 0.
- tromp 7y agoYes, that's exactly what it's for. The answer I hope for is that they don't care about the case of x==0, so that I can leave out the "x &&" part, leaving the noticeably simpler answer (x & x-1) == 0
- deleted 7y ago[deleted]
- nwallin 7y agoI did the same thing! But they didn't like it. So I wrote the naivest possible popcount and returned 1 == naive_bitcount(n). They didn't like that. I explained to them that the compiler will optimize or the loop so this will be fast and that they should check it on godbolt. (did I mention that I was coding on the white board?) There's a loop in the source code, but there isn't a loop in the machine code, and it's like three instructions. They didn't like that either, so I worked out the n & (n-1) method from first principals. I didn't do it optimally, there was some redundancy in my code, which the interviewer smugly explained to me. I can't remember if I told him "that's nice, but it's still an extra instruction compared to the trivial, obvious, easy to maintain method I showed you ten minutes ago." I'm pretty sure I didn't, too afraid to make a bad impression. I didn't get the job. In hindsight, I'm glad I didn't. Those guys are dicks.
- piadodjanho 7y agoMaybe they wanted something that worked with non integer types.
- saagarjha 7y agoBoth methods only work on integers.
- garmaine 7y agoThat was you interviewing them. They failed.
- quickthrower2 7y agoThe interviewer felt smug, so their mission was accomplished.
- AnimalMuppet 7y agoIf that was their mission (rather than to hire someone), they succeeded in their personal mission, at the expense of the company's intended mission for them.
- saagarjha 7y agoI would not be surprised if the compiler detected the second version as well and replaced it with a popcnt. In any case, it seems like you ended up with the stereotypical “bad interviewer” so I doubt it would have mattered to point this out.
- dooglius 7y agopopcnt is generally going to take multiple cycles though, I'd expect the n&(n-1) method to be more performant. It's also vectorizeable and more portable.
- dalke 7y ago
- jayd16 7y agoThis fails for negative max int, assuming twos compliment, right?
- castratikron 7y agoThe GNU __builtin_popcount takes an unsigned int. https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
- jayd16 7y agoRight. If he naively casts, it will cast to 2^(int bits size) and return 1 but that's wrong. Its not a complete solution.