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

[David T. Ashley]

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 */ );
}

 

[David T. Ashley]

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 */ );
}

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.

 

[slebetman]

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 */ );
}

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;
}

 

[pete]

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 */ );
}

int n_is_Power_of_two(long unsigned n)
{
return (n & n - 1) == 0 && n != 0;
}

 

[Richard Tobin]

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

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

 

[Eric Sosman]

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 */ );
}

"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;
}

 

[Henryk]

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

 

[Coos Haak]

Op 4 Jan 2007 03:52:16 -0800 schreef Henryk:

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

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.

 

[Daniel Pitts]

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.

int is_power_of_two(unsigned int value) {
return x && (x & (x-1))
}

 

[Clark S. Cox III]

int is_power_of_two(unsigned int value) {
return x && (x & (x-1))
}

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.

 

[Old Wolf]

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

Should be:
x && ! (x & (x-1))