Power of 2 1

[nappaji]

Does any body knows how to find if a given number is an exact power of 2???

Thanks

 

[hnd]

try this pseudocode;

int nr=nnn
bool testswt;
testswt=true;
while(nr>1 && testswt)
{
nr=nr/2;
if(nr is odd)
testswt=false
}
if(testswt)
nr is a power of 2


hnd
hasso55@yahoo.com

 

[ankan]

12/2 = 6 = not odd, but 12 is not a power of 2. there are numerous other examples.

this should work ...

#include<stdio.h>
main()
{
long num, power_of_2 = 2;

scanf(&quot;%l&quot;, num);

while(power_of_2 < num)
power_of_2 *= 2;

if (power_of_2 != num)
printf(&quot;not a &quot;

printf(&quot;power of 2\n&quot;
return 0;
} Ankan.

Please do correct me if I am wrong. s-)

 

[hnd]

Therefore i used a while loop.

12/2= 6
in the next loop
6/2=3 and that is odd.

hnd
hasso55@yahoo.com

 

[Cagliostro]

if you want an int number you can make a quick algorithm as:

unsigned int log2of(unsigned int t)
{
int i = 0;
unsigned int mask = ~(-1>>1);
int size = sizeof(int)<<3;
for(i = 0; i < size; i++)
{
if(t&(mask>>i)) return sizeof(int)<<3 - i;
}
return -1;
} John Fill

ivfmd@mail.md

 

[Zyrenthian]

Log to the base 2 would be the way to go. It has been a while but I belive

log(value)/log(2)

should give you the log to the base 2. I am 90% sure on it but as I said... it has been a while.

If there is no decimal then it is a power of 2

Matt

 

[hnd]

Thats mathematically correct, but i think there could be a Problem of rounding errors. I think, the algorithm of John Fill should do the job.
hnd
hasso55@yahoo.com

 

[Zyrenthian]

I didnt think about the possible rounding errors. I dont have time to check out what john's code is doing but I love anything binary. Thinking of this problem in binary i would think the following would work as well

int isBase2(int x)
{
if(x == 0) return 0;
int i;

// shouldnt need the i<32 check but just in case
for(i = 0; !((x>>i) & 1) && i<32;i++)
;

return ( x >> (i+1) ) == 0;
}

Matt

 

[Zyrenthian]

Just a side note, if you wanted to return the power instead of true or false just return i;

Matt

 

[nappaji]

thank you guys... really appreciate it.

 

[ankan]

Sorry hnd. My mistake. Seems like we had the same thing in mind but started from opposite ends.

John your code isn't working.

Matt yours is perfect, but maybe (like John) using sizeof(int)<<3 instead of 32 would make it better. Ankan.

Please do correct me if I am wrong. s-)

 

[brudnakm]

Nappaji,

Not to beat a dead horse, but, how about this

int isPowOf2(int i) {
    switch (abs(i)) {
        case 0x00000000:
        case 0x00000002:
        case 0x00000004:
        case 0x00000008:
        case 0x00000010:
        case 0x00000020:
        case 0x00000040:
        case 0x00000080:

        case 0x00000100:
        case 0x00000200:
        case 0x00000400:
        case 0x00000800:
        case 0x00001000:
        case 0x00002000:
        case 0x00004000:
        case 0x00008000:
      
        case 0x00010000:
        case 0x00020000:
        case 0x00040000:
        case 0x00080000:
        case 0x00100000:
        case 0x00200000:
        case 0x00400000:
        case 0x00800000:

        case 0x01000000:
        case 0x02000000:
        case 0x04000000:
        case 0x08000000:
        case 0x10000000:
        case 0x20000000:
        case 0x40000000:
        case 0x80000000:
            return TRUE ;
            break;
        default:
            return FALSE ;
            break ;
    }
}

It is a little more bulky, but is straight forward.

Hope this helps.

Brudnakm

 

[Lim]

The Simplest:

int IsAPowerOf2(int a)
{
int i = 1;
if (a&i)
return 0;
else
return 1;
}

 

[Zyrenthian]

Lim... that just tells us if it can be divided by 2 evenly. 6 in binary is 110. divisable by 2 but not a power of 2.

Matt

 

[ankan]

Here's another function I wrote that uses 2 features of C/C++ that programmers like a lot ... Recursion & Binary. It returns 1(true) or 0(false) depending on whether the number is a power of 2 or not.

int IsAPowerOf2(unsigned long a)
{
if(!(a>>1)) return 0; // for 0 & 1

int x;
x = IsAPowerOf2(a>>1);

return (a==2)? 1 : ( (x == 1) ? a^x : a&x ) & 1 ;
}

Nice and small function. Isn't it?
Perhaps, recursion may not be the way to go in this case (if so, why?), but I thought all of u would like to see this anyway.

Now, could any of u please tell me which function will be the most efficient among all of these, and why?? Ankan.

Please do correct me if I am wrong. s-)