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

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

David T. Ashley
Guest
Posts: n/a

 01-04-2007
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 == || (x == 16) /* and
so on */ );
}

David T. Ashley
Guest
Posts: n/a

 01-04-2007
"David T. Ashley" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ...
> 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 == || (x == 16) /* and
> so on */ );
> }

Let's try that again:

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

but I think everyone would have known what I meant.

slebetman@yahoo.com
Guest
Posts: n/a

 01-04-2007

David T. Ashley wrote:
> "David T. Ashley" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) ...
> > 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 == || (x == 16) /* and
> > so on */ );
> > }

>
> Let's try that again:
>
> void is_2_pow(int x)
> {
> return((x == 1) || (x == 2) || (x == 4) || (x == || (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
Guest
Posts: n/a

 01-04-2007
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 == || (x == 16) /* and
> so on */ );
> }

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

--
pete

Richard Tobin
Guest
Posts: n/a

 01-04-2007
In article <(E-Mail Removed)>,
David T. Ashley <(E-Mail Removed)> 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.

Eric Sosman
Guest
Posts: n/a

 01-04-2007
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 == || (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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Henryk
Guest
Posts: n/a

 01-04-2007
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
Guest
Posts: n/a

 01-04-2007
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

Daniel Pitts
Guest
Posts: n/a

 01-05-2007

David T. Ashley wrote:
> "David T. Ashley" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) ...
> > 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 == || (x == 16) /* and
> > so on */ );
> > }

>
> Let's try that again:
>
> void is_2_pow(int x)
> {
> return((x == 1) || (x == 2) || (x == 4) || (x == || (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
Guest
Posts: n/a

 01-05-2007
Daniel Pitts wrote:
> David T. Ashley wrote:
>> "David T. Ashley" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed) ...
>>> 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 == || (x == 16) /* and
>>> so on */ );
>>> }

>> Let's try that again:
>>
>> void is_2_pow(int x)
>> {
>> return((x == 1) || (x == 2) || (x == 4) || (x == || (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
(E-Mail Removed)