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

Discussion in 'C Programming' started by David T. Ashley, Jan 4, 2007.

1. ### David T. AshleyGuest

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, Jan 4, 2007

2. ### David T. AshleyGuest

"David T. Ashley" <> wrote in message
news:...
> 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.

David T. Ashley, Jan 4, 2007

3. ### Guest

David T. Ashley wrote:
> "David T. Ashley" <> wrote in message
> news:...
> > 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 */ );
> }

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

, Jan 4, 2007
4. ### peteGuest

David T. Ashley wrote:
>
> 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;
}

--
pete

pete, Jan 4, 2007
5. ### Richard TobinGuest

In article <>,
David T. Ashley <> wrote:

>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
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

Richard Tobin, Jan 4, 2007
6. ### Eric SosmanGuest

David T. Ashley wrote:
> 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;
}

--
Eric Sosman
lid

Eric Sosman, Jan 4, 2007
7. ### HenrykGuest

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

Henryk, Jan 4, 2007
8. ### Coos HaakGuest

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.
--
Coos

Coos Haak, Jan 4, 2007
9. ### Daniel PittsGuest

David T. Ashley wrote:
> "David T. Ashley" <> wrote in message
> news:...
> > 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.

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

Daniel Pitts, Jan 5, 2007
10. ### Clark S. Cox IIIGuest

Daniel Pitts wrote:
> David T. Ashley wrote:
>> "David T. Ashley" <> wrote in message
>> news:...
>>> 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.

>
> 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.

--
Clark S. Cox III

Clark S. Cox III, Jan 5, 2007
11. ### Old WolfGuest

Clark S. Cox III wrote:
> Daniel Pitts wrote:
> > David T. Ashley wrote:
> >> "David T. Ashley" <> wrote:
> >>> What is the most economical test in 'C' for "integer is a power of 2"?

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

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

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

Old Wolf, Jan 5, 2007