Jump to content
  • Advertisement
Sign in to follow this  
theZapper

Detect Power of two

This topic is 4834 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
For unsigned integer values, this should work:

ALGORITHM: check_p2
INPUT: x: unsigned integer
OUTPUT: "true" if x is power of two, "false" otherwise

t <- x XOR (x-1)

if( t == 2x-1 ) return true;
else retrun false;

Share this post


Link to post
Share on other sites
(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.

Share this post


Link to post
Share on other sites
1.
if ((number % 2) == 0)

2.
if ((number & 1) == 0)

Solution 2 is much faster than solution 1, but both works for unsigned types.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!