C Question: Most Economical Test For Integer Is a Power of 2

What is the most economical test in 'C' for "integer is a power of 2"?

For example, something better than:

void is_2_pow(int arg)
{
return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
so on */ );
}

re: C Question: Most Economical Test For Integer Is a Power of 2

"David T. Ashley" <dta@e3ft.comwrote in message
news:B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com ...Let's try that again:

void is_2_pow(int x)
{
return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
so on */ );
}

but I think everyone would have known what I meant.

re: C Question: Most Economical Test For Integer Is a Power of 2

David T. Ashley wrote:You're returning a value in a void function. Should be: int
is_2_pow(int x)

Probably not the most economical method, but I'd do:


int isPowerof2(int x) {
unsigned int i;
int count = 0;
int n = 1;

for (i = INT_MAX; i; i >>= 1) {
if (x & n)
count ++;
n <<= 1;
}
if (count 1)
count = 0;

return count;
}

re: C Question: Most Economical Test For Integer Is a Power of 2

David T. Ashley wrote:
int n_is_Power_of_two(long unsigned n)
{
return (n & n - 1) == 0 && n != 0;
}

--
pete

re: C Question: Most Economical Test For Integer Is a Power of 2

In article <B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com>,
David T. Ashley <dta@e3ft.comwrote:
Assuming the number is known to be 0, you can just test

x & (x-1) == 0

which tests whether there is only one bit set in x. If there's more
than one 1 bit, all but the lowest order 1 bit will be unchanged by
the subtraction and (x-1) will have 1 bits in common with x.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

re: C Question: Most Economical Test For Integer Is a Power of 2

David T. Ashley wrote:"Better than" a void function that tries to return a
value isn't much of a challenge ...

For "most economical" I nominate

int is_2_pow(int arg) { return 0; }

If you're willing to sacrifice some economy in pursuit of
correctness, you might consider

int is_2_pow(int arg) { return arg 0; }

If you're interested in a slightly more restricted problem
than the one stated, I fear you'll have to abandon all hope of
economy and suffer with this frightful piece of bloatware:

int is_2_pow(int arg) {
return arg 0 && (arg & (arg - 1)) == 0;
}

--
Eric Sosman
esosman@acm-dot-org.invalid

re: C Question: Most Economical Test For Integer Is a Power of 2

If the nummer is a power of 2 then only one bit is set in the int
value.

So just count the bits that are set and check if the number is 1. For
negative numbers it's a little more complicated...

Henryk

re: C Question: Most Economical Test For Integer Is a Power of 2

Op 4 Jan 2007 03:52:16 -0800 schreef Henryk:
There exist many negative powers of 2, but no power of 2 is negative ;-(
So if the number is negative, it surely is no power of 2. It could be a
power of -2 though.
--
Coos

re: C Question: Most Economical Test For Integer Is a Power of 2

David T. Ashley wrote:int is_power_of_two(unsigned int value) {
return x && (x & (x-1))
}

re: C Question: Most Economical Test For Integer Is a Power of 2

Daniel Pitts wrote:Hmm,

5 && (5 & (4))
== 5 && 4
== 1

15 && (15 & (14))
== 15 && 14
== 1

So, your function tells me that 5 and 15 are both powers of 2.

--
Clark S. Cox III
clarkcox3@gmail.com

re: C Question: Most Economical Test For Integer Is a Power of 2

Clark S. Cox III wrote:Should be:
x && ! (x & (x-1))