Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   C Question: Most Economical Test For Integer Is a Power of 2 (http://www.velocityreviews.com/forums/t445746-c-question-most-economical-test-for-integer-is-a-power-of-2-a.html)

 David T. Ashley 01-04-2007 01:56 AM

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

 David T. Ashley 01-04-2007 01:58 AM

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

"David T. Ashley" <dta@e3ft.com> wrote in message
news:B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com ...
> 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@yahoo.com 01-04-2007 02:29 AM

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

David T. Ashley wrote:
> "David T. Ashley" <dta@e3ft.com> wrote in message
> news:B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com ...
> > 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;
}

 pete 01-04-2007 02:55 AM

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

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

 Richard Tobin 01-04-2007 03:34 AM

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

In article <B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com>,
David T. Ashley <dta@e3ft.com> 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 01-04-2007 04:11 AM

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

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
esosman@acm-dot-org.invalid

 Henryk 01-04-2007 11:52 AM

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

 Coos Haak 01-04-2007 03:27 PM

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

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 01-05-2007 01:16 AM

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

David T. Ashley wrote:
> "David T. Ashley" <dta@e3ft.com> wrote in message
> news:B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com ...
> > 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))
}

 Clark S. Cox III 01-05-2007 03:31 AM

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

Daniel Pitts wrote:
> David T. Ashley wrote:
>> "David T. Ashley" <dta@e3ft.com> wrote in message
>> news:B4ednaLMFMNAwwHYnZ2dnUVZ_oWdnZ2d@giganews.com ...
>>> 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
clarkcox3@gmail.com

All times are GMT. The time now is 02:24 AM.