# Checking whether a number is a power of 2

39 replies to this topic

### #1john

Member

• Members
• 84 posts

Posted 25 August 2004 - 09:08 PM

bool IsPowerOfTwo (int value)
{
return (value & -value) == value;
}


### #2anubis

Senior Member

• Members
• 2225 posts

Posted 25 August 2004 - 09:10 PM

the good old trick
If Prolog is the answer, what is the question ?

### #3davepermen

Senior Member

• Members
• 1306 posts

Posted 25 August 2004 - 09:18 PM

indeed. good to get the algorithms and code snippets filled with such stuff. thats what its ment for!
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

### #4anubis

Senior Member

• Members
• 2225 posts

Posted 25 August 2004 - 09:34 PM

hmm... let's hope people use the search function in this forum, unlike other places we don't want to mention
If Prolog is the answer, what is the question ?

DevMaster Staff

• Members
• 1057 posts

Posted 25 August 2004 - 10:41 PM

another one

bool IsPowerOf2( int value )
{
return ! (value & ( value - 1 ) );
}



### #6davepermen

Senior Member

• Members
• 1306 posts

Posted 26 August 2004 - 12:33 PM

anubis said:

hmm... let's hope people use the search function in this forum, unlike other places we don't want to mention

indeed...

lets see if we find some bether solution to it.. would be nice..
davepermen.net
-Loving a Person is having the wish to see this Person happy, no matter what that means to yourself.
-No matter what it means to myself....

### #7eyebex

New Member

• Members
• 7 posts

Posted 30 October 2004 - 09:48 AM

For two more useful functions which round to the next bigger / next smaller power of two, see: http://www.flipcode.com/cgi-bin/fcarticles...show=4&id=64182

### #8thakurna

New Member

• Members
• 2 posts

Posted 30 January 2006 - 12:59 PM

john said:

bool IsPowerOfTwo (int value)
{
return (value & -value) == value;
}


It is not going to work for if the numbers are = 1, 0, -1....
Can give you solution in that case

### #9thakurna

New Member

• Members
• 2 posts

Posted 30 January 2006 - 01:01 PM

this solution will not work for if if the number = 1, 0, -1....
need some thing like return (value != 0) && (value != 1) && ( ( (value-1) & value ) == 0 );
but still need to modify

### #10.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 30 January 2006 - 01:41 PM

thakurna said:

It is not going to work for if the numbers are = 1, 0, -1....

Only not for zero. 1 & -1 == 1, which is correct as 1 is a power of two (2^0 to be exact). -1 & 1 is of course also 1, but now 'value' is -1 so the end result doesn't equal 'value', therefore it is not a power of two (this works for every negative value btw)

Only the zero is a special case. So it would be:
bool IsPowerOfTwo(int value)
{
return value ? ((value & -value) == value) : false;
}

-
Currently working on: the 3D engine for Tomb Raider.

### #11Alex

Valued Member

• Members
• 152 posts

Posted 30 January 2006 - 06:16 PM

Is a bitwise "&" consistent across platforms?? Just curious...

Alex

### #12Mihail121

Senior Member

• Members
• 1059 posts

Posted 30 January 2006 - 06:31 PM

It depends what language standards the compiler follows but for the most cases yes.

### #13eddie

Senior Member

• Members
• 751 posts

Posted 31 January 2006 - 08:11 AM

What?

I've never heard of bitwise & not being consistent. That wouldn't be "not adhering to standards", that would be a *bug*.

Unless I'm missing something. Mihail121, do you know of a compiler that doesn't handle this?

I'd find it incredible to hear that there's a "standard" that defies normal bitwise &. It's like saying that my compiler has a different standard for "+".

### #14Reedbeta

DevMaster Staff

• 5307 posts
• LocationBellevue, WA

Posted 31 January 2006 - 08:29 AM

Well, bitwise & ought to work the same way everywhere, but not all machines are two's complement and so some of the formulas posted above will not always work. (Realistically though, any machine you are going to be writing code for nowadays uses two's complement for integer arithmetic.)
reedbeta.com - developer blog, OpenGL demos, and other projects

### #15.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 31 January 2006 - 10:50 AM

Indeed, the standard requires signed ints to be either two's complement, one's complement or sign and magnitude. But that doesn't really matter, it only means we cannot use the negation operator in our test code. So either use bladder's, or this:

bool IsPowerOfTwo (int value)
{
return (value & (~value+1)) == value;  //~value+1 equals a two's complement -value
}

-
Currently working on: the 3D engine for Tomb Raider.

### #16Alex

Valued Member

• Members
• 152 posts

Posted 31 January 2006 - 12:40 PM

I wonder why there is no support for "flags" that indicate what kind of system the code has been written for (little endian, pointer size, etc etc).
That way the compiler could easily "fix" the code (or rather change the output to do what we meant it to do) if the current target doesn't fit the flags. Why is it up to us to worry about all that crap?
Using the flags it should be inherently clear what the code is supposed to do..

Sorry to high jack the thread but this is probably not worth starting a new one..

Alex

### #17tbp

Valued Member

• Members
• 135 posts

Posted 31 January 2006 - 12:54 PM

Because C has been designed to write OS with, you're supposed to know what you're doing.
As it is the Standard is byzantine enough, it doesn't need even more assumptions.

Use the right tool for a given task.
If you want more abstraction from the hardware, use another language.
If you want less, write some asm.

### #18Alex

Valued Member

• Members
• 152 posts

Posted 31 January 2006 - 01:05 PM

Now I'm probably not the only one who want's to write portable C++ code. Also the feature I suggest wouldn't stop anyone from writing OS code..it's less a language thing, more of a compiler option. There is no good reason I can see to have interpretations of my code that I have no control over but which alter the logic.

### #19tbp

Valued Member

• Members
• 135 posts

Posted 31 January 2006 - 01:16 PM

Alex said:

it's less a language thing, more of a compiler option.
If it's not into the language/standard, then it's not portable across compilers.

So either you don't want to have to handle such issues and use another language that insulates you better, or rely on something like autoconf.

Alex said:

There is no good reason I can see to have interpretations of my code that I have no control over but which alter the logic
The only logic that is altered is the one you _think_ your code implements.
The compiler only care about how your code should be interpreted vs the Standard.

### #20.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 31 January 2006 - 01:49 PM

tbp: you are missing the point. For example, the standard states that the number of bits in a char shall be 8 or more. Fortunately, the standard also states that there shall be a CHAR_BIT constant representing the number of bits in a char. It also defines other handy constants like INT_MAX. These are all pretty implementation defined, but the point is that you have access to such constants, so you can write portable code that runs on different architectures using these constants.

Unfortunately for endianness and how signed integers are represented, there is no such thing.