to test whether a number is a power of 2

[ravi]

Give a one-line C expression to test whether a number is a power of 2.
[No loops allowed]

[Walter Roberson]

In article <pi************ @news.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.ukwro te:

>Eric Sosman wrote, On 08/07/07 13:27:

>ravi wrote:

>>On Jul 8, 10:22 am, Martin Ambuhl <mamb...@earthl ink.netwrote:
ravi wrote:
Give a one-line C expression to test whether a number is a power of 2.
[No loops allowed]

>Probably. Had you enough sense you would have instantly known the answer
was:

>int powerof2( double num ) { return 1; }

>After all, the OP did not specify integer power of 2, or even real power
of 2, and I think if you allow complex powers, all numbers will qualify.

But the OP did specify that the expression be one-line. Even if we
were to restrict our use of "number" to "the numbers representable
in C", since C does not have any run-time typing (RTT), I don't think
it would be possible to write a one-line expression that would take
an arbitrary number (of -any- of the valid C numeric types) as parameter
and return any meaningful information about it. If we could at least
receive the number as a void* and a type indicator, we could unionize
and ?: the problem to death.
--
Programming is what happens while you're busy making other plans.

[Kenneth Brody]

Walter Roberson wrote:

>
In article <pi************ @news.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.ukwro te:

Eric Sosman wrote, On 08/07/07 13:27:

ravi wrote:
On Jul 8, 10:22 am, Martin Ambuhl <mamb...@earthl ink.netwrote:
ravi wrote:
Give a one-line C expression to test whether a number is a power of 2.
[No loops allowed]

[...]

int powerof2( double num ) { return 1; }

After all, the OP did not specify integer power of 2, or even real power
of 2, and I think if you allow complex powers, all numbers will qualify.

But the OP did specify that the expression be one-line. Even if we
were to restrict our use of "number" to "the numbers representable
in C", since C does not have any run-time typing (RTT), I don't think
it would be possible to write a one-line expression that would take
an arbitrary number (of -any- of the valid C numeric types) as parameter
and return any meaningful information about it. If we could at least
receive the number as a void* and a type indicator, we could unionize
and ?: the problem to death.

Why not a macro?

#define POWEROF2(value) (1)

However, can zero be expressed as a power of 2? (I suppose raising 2
to the power of negative infinity may qualify, but I'm not certain.)

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer .h|
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:Th***** ********@gmail. com>

[Walter Roberson]

In article <pi************ @news.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.ukwro te:

>Had you enough sense you would have instantly known the answer
was:

>int powerof2( double num ) { return 1; }

>After all, the OP did not specify integer power of 2, or even real power
of 2, and I think if you allow complex powers, all numbers will qualify.

Hey, I just realized that the specification required that the
expression -test- that the number was a power of 2, but the
specification didn't require that the expression evaluated to
anything in particular either way -- or even that the expression
got the test right in any or all cases.

For example, we commonly speak of "testing whether a number is prime"
and in a number of cases are satisfied if the test is looking for
"obvious" non-primes, something fast as a filter to keep us from
having to use slower but more complete algorithms.
--
Is there any thing whereof it may be said, See, this is new? It hath
been already of old time, which was before us. -- Ecclesiastes

[Flash Gordon]

Kenneth Brody wrote, On 10/07/07 18:52:

Walter Roberson wrote:

>In article <pi************ @news.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.ukwro te:

>>Eric Sosman wrote, On 08/07/07 13:27:
ravi wrote:
On Jul 8, 10:22 am, Martin Ambuhl <mamb...@earthl ink.netwrote:
>ravi wrote:
>>Give a one-line C expression to test whether a number is a power of 2.
>> [No loops allowed]

[...]

>>int powerof2( double num ) { return 1; }
After all, the OP did not specify integer power of 2, or even real power
of 2, and I think if you allow complex powers, all numbers will qualify.

But the OP did specify that the expression be one-line. Even if we
were to restrict our use of "number" to "the numbers representable
in C", since C does not have any run-time typing (RTT), I don't think
it would be possible to write a one-line expression that would take
an arbitrary number (of -any- of the valid C numeric types) as parameter
and return any meaningful information about it. If we could at least
receive the number as a void* and a type indicator, we could unionize
and ?: the problem to death.

Why not a macro?

#define POWEROF2(value) (1)

However, can zero be expressed as a power of 2? (I suppose raising 2
to the power of negative infinity may qualify, but I'm not certain.)

You could check for 0 then.
#define POWEROF2(value) ((value)!=0)

Hard to do something that will cope with inf and NaN for both complex
and doubles in C99, but we could lobby for adding type-generic versions
of isnan and isinf to C0x to solve this problem.
--
Flash Gordon

[Flash Gordon]

Walter Roberson wrote, On 10/07/07 19:09:

In article <pi************ @news.flash-gordon.me.uk>,
Flash Gordon <sp**@flash-gordon.me.ukwro te:

>Had you enough sense you would have instantly known the answer
was:

>int powerof2( double num ) { return 1; }

>After all, the OP did not specify integer power of 2, or even real power
of 2, and I think if you allow complex powers, all numbers will qualify.

Hey, I just realized that the specification required that the
expression -test- that the number was a power of 2,

See elsethread where I added some tests. Specifically for inf, NaN and 0.

but the
specification didn't require that the expression evaluated to
anything in particular either way -- or even that the expression
got the test right in any or all cases.

OK, replace the 1 by (num!=atan(num) )

For example, we commonly speak of "testing whether a number is prime"
and in a number of cases are satisfied if the test is looking for
"obvious" non-primes, something fast as a filter to keep us from
having to use slower but more complete algorithms.

Oh, you were thinking of the less accurate test being faster. <shrug>
Well, that was not in the original spec either.
--
Flash Gordon

[Keith Thompson]

Flash Gordon <sp**@flash-gordon.me.ukwri tes:

Kenneth Brody wrote, On 10/07/07 18:52:

[...]

>Why not a macro?
#define POWEROF2(value) (1)
However, can zero be expressed as a power of 2? (I suppose raising 2
to the power of negative infinity may qualify, but I'm not certain.)

You could check for 0 then.
#define POWEROF2(value) ((value)!=0)

Or, more simply:

#define POWEROF2(value) (value)

Both forms have the interesting property of treating non-null pointers
as powers of 2.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[pete]

ravi wrote:

>
Give a one-line C expression to test whether a number is a power of 2.
[No loops allowed]

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

int n_is_Power_of_f our(long unsigned n)
{
return (n & n - 1) == 0 && n % 3 == 1;
}

int n_is_Power_of_e ight(long unsigned n)
{
return (n & n - 1) == 0 && n % 7 == 1;
}

--
pete

[Flash Gordon]

Keith Thompson wrote, On 10/07/07 21:49:

Flash Gordon <sp**@flash-gordon.me.ukwri tes:

>Kenneth Brody wrote, On 10/07/07 18:52:

[...]

>>Why not a macro?
#define POWEROF2(value) (1)
However, can zero be expressed as a power of 2? (I suppose raising 2
to the power of negative infinity may qualify, but I'm not certain.)

You could check for 0 then.
#define POWEROF2(value) ((value)!=0)

Or, more simply:

#define POWEROF2(value) (value)

Both forms have the interesting property of treating non-null pointers
as powers of 2.

Perhaps that will help those people who want to do strange things
because the believe (incorrectly) that pointers are just integers then :-)
--
Flash Gordon

[CBFalconer]

Christopher Benson-Manica wrote:

CBFalconer <cb********@yah oo.comwrote:
[OP wrote:]

>>Give a one-line C expression to test whether a number is a power
of 2.

>I like my version better :-) In all seriousness, this is not such
a simple thing, so I doubt it was homework. If he hadn't used such
rude terminology I would be virtually sure it is not.

Given the number of ridiculous questions that are routinely asked here
that clearly *are* homework, I'm surprised you find it unlikely that
the above question is not homework. Why else would there be
constraints such as "one line" or "no loops allowed" (snipped from
above context)? I personally find it highly unlikely that anyone
asking the question seriously would phrase it so tersely.

You have a definite point, and are probably right.

--
<http://www.cs.auckland .ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfoc us.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net

--
Posted via a free Usenet account from http://www.teranews.com

[Army1987]

On Mon, 09 Jul 2007 08:13:20 +0100, Flash Gordon wrote:

Harald van Dijk wrote, On 08/07/07 23:37:

>Flash Gordon wrote:

>>Probably. Had you enough sense you would have instantly known the answer
was:

int powerof2( double num ) { return 1; }

After all, the OP did not specify integer power of 2, or even real power
of 2, and I think if you allow complex powers, all numbers will qualify.

What about zeroes, infinities, and NaNs? I would think it should return 0
for those.

Zero is easy to deal with, infinities could be argued as being powers of
2, [snip]

The argument about infinities also applies to zero. The difference
is just the sign of the exponent.

--
Army1987 (Replace "NOSPAM" with "email")
"Never attribute to malice that which can be adequately explained
by stupidity." -- R. J. Hanlon (?)