
Hi All,
Is there a fast way of checking to see if an int is a power of 2 (i.e. 2, 4, 8, 16, 1024)? I know the long way using a loop, but I was hoping for a simple way of doing this.
regards,
Rich
"Programming today is a race between software engineers striving to build bigger and
better idiotproof programs, and the Universe trying to produce bigger and better idiots.
So far the Universe is winning."  Rich Cook






Thanks
"Programming today is a race between software engineers striving to build bigger and
better idiotproof programs, and the Universe trying to produce bigger and better idiots.
So far the Universe is winning."  Rich Cook





I think you will have problems when comparinf the floats, due to the precision.





true, but that was a starting point.
it would be better to use double at least, but still remains the precision problem.





2^3 = 8
but
floor(sqrt(8)) != sqrt(8)?
Steve





Modified version is still wrong  It will treat any integer as a power of 2.
Steve





i did not pretend to modified my post for a much working stuff...





if a number is a power of 2 than looking at the bits that composed that value must be all '0' but only one '1'.
So, if int is a 32 bit value, you can look for 31 '0' and 1 '1'.
But you need olso a loop! But it is quite fast.
Let me know if here is a faster bit function to count the ones/zeros
Bye
Have a nice code day





Yip, this was my way to begin with.
regards,
Rich
"Programming today is a race between software engineers striving to build bigger and
better idiotproof programs, and the Universe trying to produce bigger and better idiots.
So far the Universe is winning."  Rich Cook





Read this function, it could be another start point!
This function that I wrote last year find the bigger long, greater than the input value, that is a power of 2.
And it is quite fast!
unsigned long Next2Power(unsigned long x){<br />
unsigned long y=1, x1=x;<br />
if(x==0) return 0;<br />
while(x1!=0){<br />
x1>>=1;<br />
y<<=1;<br />
}<br />
y>>=1;<br />
if(y!=x) y<<=1;<br />
return y;<br />
}
Have a nice code day





_Russell_ wrote: This function that I wrote last year find the bigger long, greater than the input value, that is a power of 2.
Why not just use log<sub>2</sub>() ?
"Let us be thankful for the fools. But for them the rest of us could not succeed."  Mark Twain
"There is no death, only a change of worlds."  Native American Proverb





Because my function is faster (I think) than log2().
But if I'm wrong let me know how have a faster function. And why.
thanks
Have a nice code day





_Russell_ wrote: ...let me know how have a faster function.
This one benchmarks faster than the one you've shown:
unsigned long Next2Power(unsigned long x)
{
x;
x = x >> 1;
x = x >> 2;
x = x >> 4;
x = x >> 8;
x = x >> 16;
x++;
return x;
}
"Let us be thankful for the fools. But for them the rest of us could not succeed."  Mark Twain
"There is no death, only a change of worlds."  Native American Proverb





Hello RichardS,
Try this one.
double val = 0.0;
val = log10(y) / log10(2.0);
int val2 = int(val);
if (val == val2)
else
here 'y' is value u want to check for power of 2.
Best of luck
Divyang Mithaiwala
System Engineer & Software Developer





we are on a standard C++ forum, not managed/CLI...





Hello v2.0,
We are on visual C++ & my suggesion is not wrong for it.
Divyang Mithaiwala
System Engineer & Software Developer





Divyang Mithaiwala wrote: my suggesion is not wrong for it.
yes it is, it will not work on a MFC/Win32 project...
it is only for managed C++ (which is not for this forum, but for the C++/CLI forum instead)





Here logic is simple
y = value that want to check
x = find a value that is in power of 2
so,
2^x = y
log 2^x = log y
x log 2 = log y
x = log y /log 2
Divyang Mithaiwala
System Engineer & Software Developer





Hi,
you could use ::log to check if its a power of 2
math:
y = 2^x > x = log(y)/log(2)
so you can use:
int y = 1024;
if(y == (int)(::pow(2.0, ::floor(::log((double)y)/::log(2.0)))))
{
}
else
{
}
but his is heavy processing,
so it mith be slower that the for loop
codito ergo sum





Define "fast".
If you're using 32bit int's, there are only 32 possibilities so you can just check entries in a lookup table, making sure you do the most likely candidates first.
BTW, all these suggestions to use sqrt() and log() are nuts  these functions are insanely slow!
The two most common elements in the universe are Hydrogen and stupidity.  Harlan Ellison
Awasu 2.2 [^]: A free RSS/Atom feed reader with support for Code Project.





Taka Muraoka wrote: BTW, all these suggestions to use sqrt() and log() are nuts  these functions are insanely slow!
Agreed!! It is quite simple. A single decrement and bitwise AND will do the job nicely
Ryan "Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late" John Nichol "Point Of Impact"





Crikey. I thought this was well known. Just do this:
if (x & (x1))
{
}
else
{
}
sorry, got the two cases round the wrong way...
Ryan "Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late" John Nichol "Point Of Impact"
 modified at 6:04 Monday 6th March, 2006





This is by far the best suggestion so far  I'd wager it's impossible to beat this technique.
Steve





And yet it got the lowest votes of all of them. Funny, isn't it
Ryan "Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late" John Nichol "Point Of Impact"



