Power of Two ??

Tobias Kilian

unread,

Sep 29, 2002, 9:30:42 AM9/29/02

to

Hi NG !

I wonder what's the fast way to check if an int is a power of 2 ??
I want to use GL_TEXTURE_RECTANGLE_NV only if needed.

I think there could be a bitwise solution, because
x is power of 2 == only one bit of x is 1 !?

So, how are you doing it ??

I know i can just do it like in the following code, but then returning
false means 12 comparisons. (yeah, that's not much today, and the code is
only called if a new texture is generated, but...well, I was just
wondering...)

bool isPowerOfTwo(int aInt)
{
switch (aInt)
{
case 2 :
case 4 :
case 8 :
case 16 :
case 32 :
case 64 :
case 128 :
case 256 :
case 512 :
case 1024 :
case 2048 :
case 4096 :
return true;
};
return false;
}

Dave Eberly

unread,

Sep 29, 2002, 9:58:04 AM9/29/02

to

"Tobias Kilian" <gun...@uni-koblenz.de> wrote in message
news:Xns92989DE...@130.133.1.4...

> I wonder what's the fast way to check if an int is a power of 2 ??

bool isPowerOfTwo(int aInt)
{
// assert: aInt > 0
return (aInt & -aInt) == aInt;
}

--
Dave Eberly
ebe...@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com

Ruud van Gaal

unread,

Sep 29, 2002, 10:23:20 AM9/29/02

to

On 29 Sep 2002 13:30:42 GMT, Tobias Kilian <gun...@uni-koblenz.de>
wrote:

>Hi NG !
>
>I wonder what's the fast way to check if an int is a power of 2 ??
>I want to use GL_TEXTURE_RECTANGLE_NV only if needed.
>
>I think there could be a bitwise solution, because
>x is power of 2 == only one bit of x is 1 !?
>
>So, how are you doing it ??
>
>I know i can just do it like in the following code, but then returning
>false means 12 comparisons.

A switch can be done with conditional jumps sometimes, but I don't
think it can here. Dave's suggestion looks a lot quicker. :)

Ruud van Gaal
Free car sim: http://www.racer.nl/
Pencil art : http://www.marketgraph.nl/gallery/

Tobias Kilian

unread,

Sep 29, 2002, 1:01:57 PM9/29/02

to

Respect, and many thanks !

zed

unread,

Sep 29, 2002, 10:25:11 PM9/29/02

to

great its gonna make your program run100x quicker :)

>>I wonder what's the fast way to check if an int is a power of 2 ??

>>I want to use GL_TEXTURE_RECTANGLE_NV only if needed.

i just wanna point out the old programming saying
'premature optimization is the root of all evil'

learn it, itll save lots of heartache.

zed

yomgui

unread,

Sep 30, 2002, 10:05:46 AM9/30/02

to

Dave Eberly wrote:
>
> "Tobias Kilian" <gun...@uni-koblenz.de> wrote in message
> news:Xns92989DE...@130.133.1.4...
> > I wonder what's the fast way to check if an int is a power of 2 ??
>
> bool isPowerOfTwo(int aInt)
> {
> // assert: aInt > 0
> return (aInt & -aInt) == aInt;
> }

I must be stupid, but I just don't get it

aInt = 5 ( 00000101 )
-aInt = -5 ( 10000101 )
(aInt & -aInt) = ( 00000101 ) 5

where I am wrong ?

thanks

yomgui

--
1011010111 100101 101000100111

17606291711815434037934881872331611670777491166445300472749449436575622328171096762265466521858927
*
40099499726183758517891939428601665707063794593443940689888526556802581529262728143398959743444150539520890742947533452401

Thore B. Karlsen

unread,

Sep 30, 2002, 10:25:48 AM9/30/02

to

On Mon, 30 Sep 2002 16:05:46 +0200, yomgui <n...@valid.com> wrote:

>> > I wonder what's the fast way to check if an int is a power of 2 ??

>> bool isPowerOfTwo(int aInt)
>> {
>> // assert: aInt > 0
>> return (aInt & -aInt) == aInt;
>> }

>I must be stupid, but I just don't get it
>
> aInt = 5 ( 00000101 )
>-aInt = -5 ( 10000101 )
>(aInt & -aInt) = ( 00000101 ) 5
>
>where I am wrong ?

Look up "two's complement" on the web. The binary representation of a
negative number does not differ by just the most significant bit.

--
Be seeing you.

Stig R Kristiansen

unread,

Sep 30, 2002, 10:50:55 AM9/30/02

to

"yomgui" <n...@valid.com> wrote in message
news:3D985A3A...@valid.com...

> Dave Eberly wrote:
> >
> > "Tobias Kilian" <gun...@uni-koblenz.de> wrote in message
> > news:Xns92989DE...@130.133.1.4...
> > > I wonder what's the fast way to check if an int is a power of 2 ??
> >
> > bool isPowerOfTwo(int aInt)
> > {
> > // assert: aInt > 0
> > return (aInt & -aInt) == aInt;
> > }
>
> I must be stupid, but I just don't get it
>
> aInt = 5 ( 00000101 )
> -aInt = -5 ( 10000101 )
> (aInt & -aInt) = ( 00000101 ) 5
>

aInt = 5 (00000101)
-aInt = -5 (11111011) (here you got it wrong)
(aInt & -aInt) = 1 (00000001)

yomgui

unread,

Sep 30, 2002, 10:51:33 AM9/30/02

to

> Look up "two's complement" on the web. The binary representation of a
> negative number does not differ by just the most significant bit.

thanks.