# 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.

## 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 on other sites
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;

##### 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 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 on other sites
Quote:
 Original post by nife1.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 on other sites
Woops, misread (quite badly I can see) the text, sorry..

##### Share on other sites
Quote:
 Original post by nife1.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 on other sites
holy crap I was not beated to the post, I was ANNIHILATED!

##### 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 on other sites
bool IsPowOf2(Uint32 a)
{
if(a & ~a)return false;
return true;
}

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633387
• Total Posts
3011620
• ### Who's Online (See full list)

There are no registered users currently online

×