Power of 2

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

[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

[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

[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"

[Stephen Hewitt]

I gave you a 5 - I would have left it at that but then I saw the low score and felt compelled to reply. Steve

[Nibu babu thomas]

Yeah, well said.

---

Nibu thomas Software Developer

[Ryan Binns]

Thanks :) I don't really care. I assume it was because of my first sentence. I was just surprised that five people answered, but not one of them knew about this. I genuinely believed it was well known!

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"