Power of 2
-
Hi All, Is there a fast way of checking to see if an
intis 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 CookDefine "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.
-
Hi All, Is there a fast way of checking to see if an
intis 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 CookCrikey. 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
-
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
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 ;)
-
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
This is by far the best suggestion so far - I'd wager it's impossible to beat this technique. Steve
-
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.
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 & (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
Great work! You've implemented Russel's idea!
Nibu thomas Software Developer
-
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"
-
Great work! You've implemented Russel's idea!
Nibu thomas Software Developer
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"
-
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"
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
-
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"
Yeah, well said.
Nibu thomas Software Developer
-
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
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"
-
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"
Surely using the word "crikey" demands higher rather than lower scores! Steve
-
Surely using the word "crikey" demands higher rather than lower scores! Steve
:laugh:!
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"
-
Hello v2.0, We are on visual C++ & my suggesion is not wrong for it.
Divyang Mithaiwala System Engineer & Software Developer
-
Hello v2.0, We are on visual C++ & my suggesion is not wrong for it.
Divyang Mithaiwala System Engineer & Software Developer
-
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"
Hi Ryan, Thanks for the help. The code is great and the application is for an embedded -> PC interface. cheers 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
-
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
Hi Ryan, Is there is quick way for now making x a power of 2 after you have decided that it is not? 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
-
Modified version is still wrong - It will treat any integer as a power of 2. Steve
-
Modified version is still wrong - It will treat any integer as a power of 2. Steve
-
Hi All, Is there a fast way of checking to see if an
intis 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#define ISPOWER2(x) (!((x)&((x)-1)))
"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