• Advertisement

# [C++] Fast Power of 2 Test

This topic is 4226 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

I need a fast method that will test if a number is a power of 2. So far the fastest method I can think of would be using the std::bitset<> templated container class like this:
bool IsPower2(int number)
{
std::bitset<32> bit_set(number);

return (bit_set.count()<2);
}

Is this method effecient or is there a faster way?

#### Share this post

##### Share on other sites
Advertisement
I found this method here

bool IsPower2(int x)
{
return ( (x > 0) && ((x & (x - 1)) == 0) );
}

#### Share this post

##### Share on other sites
int a;

!(a & (--a)) && a;

#### Share this post

##### Share on other sites
Thanks, I thought there was a neat little bit manipulation trick to do it. Easier than I thought though.

#### Share this post

##### Share on other sites
Quote:
 Original post by Anonymous Posterint a;!(a & (--a)) && a;

Do not do it like this, it enters into undefined evaluation order territory.

Nicksterdomus's method is fine though.

#### Share this post

##### Share on other sites
bool is_pow2(const int x) { return ((x & -x) == x); }

#### Share this post

##### Share on other sites
Quote:
Original post by Null and Void
Quote:
 Original post by Anonymous Posterint a;!(a & (--a)) && a;

Do not do it like this, it enters into undefined evaluation order territory.

Nicksterdomus's method is fine though.

While it should be
!(a & (a-1)) && a
(since the AP's doesn't work)

I don't see the undefined evaulation order.
I looks like it's properly defined as
a1=a-1
a2=a1&a1 //Why the AP's version doesn't work
a3=!a2
answer = a3 && a1

#### Share this post

##### Share on other sites
Quote:
 Original post by Anonymous Posterint a;!(a & (--a)) && a;

a &(a-1) == 0

(1000 & 0111)==0000

#### Share this post

##### Share on other sites
!(a & (--a)) && a;

Quote:
 Original post by CocalusI don't see the undefined evaulation order.

Consider a == 2. The two possible results are:

!(2 & 1) && 1 -> 1

!(1 & 1) && 1 -> 0

Depending on whether (--a) or (a) is evaluated first in the leftmost expression.

#### Share this post

##### Share on other sites
*edit: ToohrVyk's explanation is much clearer than my own, and took less time to generate.
Quote:
 Original post by CocalusI don't see the undefined evaulation order.I looks like it's properly defined asa1=a-1a2=a1&a1 //Why the AP's version doesn't worka3=!a2answer = a3 && a1

It looks that way, but it isn't. You did a splendid job of illustrating why. The APs version would work, if it spread out thusly:

a1=a-1
a2=a&a1 //Why the APs version does work
a3=!a2
answer=a3&a1

But you don't know how it gets expanded. And so the result is undefined.

CM

#### Share this post

##### Share on other sites
I didn't realize that the problems with ++a + ++a, applied with a single ++ operator. Makes sense now that I think about it though.

#### Share this post

##### Share on other sites
I use this:

bool isPowerOfTwo(int n)
{
return !(n & (n - 1)); //this checks if the integer n is a power of two or not
}

But beware that this method works correctly for every n, except for n == 0, because I left the 0-test out since it wasn't needed in my case.

#### Share this post

##### Share on other sites
one could however argue that 0 is a power of two for int's ;)

#### Share this post

##### Share on other sites
Quote:
 Original post by LtJaxone could however argue that 0 is a power of two for int's ;)

Well, powers of 2 are generated by taking 2 and multiplying it by itself n times (n in [-inf,+inf[; if you restrict yourself to integers, n is is [0,+inf[). There's no way you can get 0 using this, thus 0 is not a power of 2. 1 is.

So:

bool isPowerOfTwo(int n)
{
return (n) && !(n & (n - 1)); //this checks if the integer n is a power of two or not
}

Works for 0 now [smile]

Regards,

#### Share this post

##### Share on other sites
Quote:
 Original post by LtJaxone could however argue that 0 is a power of two for int's ;)

One could argue a lot of things, but one would be foolish to do so.

CM

#### Share this post

##### Share on other sites
Actually 0 = 2^32 (on a 32-bit machine):

int main() {
int i, n = 1;
for(i=0; i<32; i++) n *= 2;
printf("2^32 = %d\n", n);
}

#### Share this post

##### Share on other sites
Quote:
 Original post by MateiActually 0 = 2^32 (on a 32-bit machine):int main() { int i, n = 1; for(i=0; i<32; i++) n *= 2; printf("2^32 = %d\n", n);}

C++ doesn't have its own definition of powers. 2^32 is 4 294 967 296. Also 32 bit machines may have sizeof(long) set to 8. Also the result of your code is undefined; the value of signed int objects which has overflown is undefined.

#### Share this post

##### Share on other sites
Quote:
Original post by CTar
Quote:
 Original post by MateiActually 0 = 2^32 (on a 32-bit machine):int main() { int i, n = 1; for(i=0; i<32; i++) n *= 2; printf("2^32 = %d\n", n);}

C++ doesn't have its own definition of powers. 2^32 is 4 294 967 296. Also 32 bit machines may have sizeof(long) set to 8. Also the result of your code is undefined; the value of signed int objects which has overflown is undefined.

A stronger case could be made that 0 is a power of 2 for unsigned int's since they are required to follow modulo arithmetic.

#### Share this post

##### Share on other sites
Quote:
 Original post by Null and Void...

!

A Null and Void sighting!

He is alive!

#### Share this post

##### Share on other sites
Did you know that for unsigned char objects, 255 < 0? Its true. 255+1 == 0, therefore 255 is one less than zero. Be sure to keep that in mind next time you implement an isLessThanZero function.

CM

#### Share this post

##### Share on other sites
Quote:
 Original post by Conner McCloudDid you know that for unsigned char objects, 255 < 0? Its true. 255+1 == 0, therefore 255 is one less than zero. Be sure to keep that in mind next time you implement an isLessThanZero function.

Yeah, "is less than" isn't very well defined in modulo arithmetic.

#### Share this post

##### Share on other sites
Isn't there a bitscan trick or something for doing this on x86?

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement
• ### Popular Tags

• Advertisement
• ### Popular Now

• 11
• 11
• 22
• 11
• 15
• Advertisement