• Advertisement
Sign in to follow this  

[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


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
int a;

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

Share this post


Link to 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


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
int 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


Link to post
Share on other sites
Quote:
Original post by Null and Void
Quote:
Original post by Anonymous Poster
int 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


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
int a;

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


a &(a-1) == 0

(1000 & 0111)==0000

Share this post


Link to post
Share on other sites
!(a & (--a)) && a;

Quote:
Original post by Cocalus
I 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


Link to 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 Cocalus
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

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


Link to 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


Link to 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


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

Share this post


Link to post
Share on other sites
Quote:
Original post by LtJax
one 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


Link to post
Share on other sites
Quote:
Original post by LtJax
one 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


Link to 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


Link to post
Share on other sites
Quote:
Original post by Matei
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);
}


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


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by CTar
Quote:
Original post by Matei
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);
}


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


Link to 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


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Conner McCloud
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.


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

Share this post


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

  • Advertisement