Power of 2

RichardS

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 idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far the Universe is winning." -- Rich Cook

toxcct

:sigh:

Russell

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 ;)

RichardS

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

RichardS

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

Cedric Moonen

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

Divyang Mithaiwala

Hello RichardS, Try this one.

double val = 0.0;
val = log10(y) / log10(2.0);

//Check that 'val' is pure int (Here you use ur own code is u optimize)
int val2 = int(val);

if (val == val2) 
     // y is power of 2
else
     // y is not power of 2

here 'y' is value u want to check for power of 2. Best of luck

Divyang Mithaiwala System Engineer & Software Developer

Stephen Hewitt

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

toxcct

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

toxcct

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

BadKarma

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)))))
{
  //  true
}
else
{
  // false
}

but his is heavy processing, so it mith be slower that the for loop codito ergo sum

Divyang Mithaiwala

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

Taka Muraoka

Define "fast". If you're using 32-bit 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.

Ryan Binns

Crikey. I thought this was well known. Just do this:

if (x & (x-1))
{
// x is <edit>not</edit>a power of two
}
else
{
// x is <edit>not</edit> a power of two
}

sorry, got the two cases round the wrong way... :-O

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

Russell

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){ unsigned long y=1, x1=x; if(x==0) return 0; while(x1!=0){ x1>>=1; y<<=1; } y>>=1; if(y!=x) y<<=1; return y; }

Have a nice code day ;)

Stephen Hewitt

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

Ryan Binns

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"

Nibu babu thomas

Great work! You've implemented Russel's idea!

Nibu thomas Software Developer

Ryan Binns

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"

Ryan Binns

Actually, I've been using this for years doing embedded programming. Every clock cycle is precious ;)

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"