Archived

This topic is now archived and is closed to further replies.

Sphere

is x a power of 2???

Recommended Posts

Hi guys, How do I determine if x is a power of 2 or not? I know about testing it with logarithm, is there any other way to do this? like manipulating the bits or something? Ok, thanks a lot for the time.

Share this post


Link to post
Share on other sites
Observe the relation between base 10 and base 2 numbers:
1=(2^0)=1
2=(2^1)=10
4=(2^2)=100
8=(2^3)=1000
16=(2^4)=10000
32=(2^5)=100000
64=(2^6)=1000000
128=(2^7)=10000000
256=(2^8)=100000000
512=(2^9)=1000000000 (etc.)

The pattern is clear, and if you don't want to use a built in library function (e.g. exponentiation or logarithm), then it's up to you to code a bit-twiddling function to serve your specific needs. Good luck.

[edit] f**ckin' ascii formatting!! [/edit]

Edited by - Graylien on October 4, 2000 10:37:45 AM

Share this post


Link to post
Share on other sites

int ispowof2(unsigned long n)
{
int b, count;

count = 0;
for(b=0; b<32; b++)
{
if(n & 1)
count++;
n = n >> 1;
}

if(count == 1)
return(1);
return(0);
}

Share this post


Link to post
Share on other sites
If x is an integer, (x&(x-1))==0 returns true if x is a power of 2.

if x is a float or a double, x is a power of two if the mantissa = 0.

MSN

Share this post


Link to post
Share on other sites
    
bool ispow2(int n) {
if(n&0FFFF ==0) n>>=16;
if(n&0FF ==0) n>>=8;
if(n&0F ==0) n>>=4;
while(n)
if(n&1) return n==1;
else n >>= 1;
}


It would be interesting to see how this compares to assembly.
3 compares and shifts to insure at least 1 bit in the low order nibble, at most 4 loops to shift this to the least significant bit. It would take a million trials before you would notice a difference with Novalises code, I just felt like twiddleing.

Share this post


Link to post
Share on other sites
quote:
Original post by Buster

MSN: nice!

bool isPow2(int x) {
return !(x&(x-1));
}



Careful, it should be

bool isPow2(unsigned int x)
{
return !(x&(x-1));
}

note 2 << 31 is negative if signed. Thanks MSN, that is pretty interesting...

Mike

Share this post


Link to post
Share on other sites