Detect Power of two
Author
Hi
I've been to some interviews lately and been asked this question twice. 'How do you quickly detect if a number is a power of two?'.
The only way I can think of is to scan the bits and if there is more than one 1, it's not a power of two. Both places didn't tell me the answer so I'd just like to know for future reference.
Thanks
For unsigned integer values, this should work:
ALGORITHM: check_p2INPUT: x: unsigned integer OUTPUT: "true" if x is power of two, "false" otherwiset <- x XOR (x-1)if( t == 2x-1 ) return true;else retrun false;
(v & (v - 1)) == 0;
and Clicky
Bad interview question though. The only thing it really tests is if you've seen that trick before. I don't think many people would be able to think of that one on the spot.
and Clicky
Bad interview question though. The only thing it really tests is if you've seen that trick before. I don't think many people would be able to think of that one on the spot.
1.
if ((number % 2) == 0)
2.
if ((number & 1) == 0)
Solution 2 is much faster than solution 1, but both works for unsigned types.
if ((number % 2) == 0)
2.
if ((number & 1) == 0)
Solution 2 is much faster than solution 1, but both works for unsigned types.
Quote:Original post by nife
1.
if ((number % 2) == 0)
2.
if ((number & 1) == 0)
Solution 2 is much faster than solution 1, but both works for unsigned types.
Those just check if it's a multiple of 2, not a power. ((6 % 2) == 0) (TRUE), but 6 is not a power of 2.
Quote:Original post by nife
1.
if ((number % 2) == 0)
2.
if ((number & 1) == 0)
Solution 2 is much faster than solution 1, but both works for unsigned types.
I believe that solution 2 is incorrect:
12 is not power of 2, and 12 looks like 1100 in binary
12 == 1100, but (1100 & 1) == 0 so the test is incorrect. (I think)
Author
Thanks pinacolada, I'll try and remember that if I get it again.
I thought it was a bit of a stupid question too, but I've had a few where I'm sat there thinking 'How am I supposed to know that if I've never worked in the game industry?'
Oh well, cheers everyone anyway
I thought it was a bit of a stupid question too, but I've had a few where I'm sat there thinking 'How am I supposed to know that if I've never worked in the game industry?'
Oh well, cheers everyone anyway
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
