Determine if an int is a power of 2 or not in a single line

Question

Possible Duplicate:
How to check if a number is a power of 2

I made the following code, but it's not working. The compiler gives an error that for a missing ) and expression syntax error. What is the the procedence of the operators? From left to right or right to left?

#include <stdio.h>
#include <limits.h>
#include <math.h>
int main()
{
    int i, x = 256, y, flag;
    for (i = 0, flag = 0, y = 1; y<INT_MAX; if (flag) break, if (flag) printf("YES"), if(y == x) flag = 1, i++, y = pow(2,i));
    return 0;
}

[There is a very simple solution to this problem.](http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2) — James McNellis, Sep 03 '10 at 18:14
@fahad: You clearly did not read the question and answers to which I linked. — James McNellis, Sep 03 '10 at 18:17
@fahad: the highest voted answer to that link works in one line if you don't wrap it in a function. Nor is a "line" a fundamental unit of c code: just leave out the newlines and everything between preprocessor directives fits on "one line". — dmckee --- ex-moderator kitten, Sep 03 '10 at 18:18
@james, The link provided is an excellent solution, not that i have chance to read up and understand it. Good find :) — JonWillis, Sep 03 '10 at 18:22
Since the real question here is the diagnosis of the mal-formed for loop, should the question be tweaked to make the power of two test background for "where is the syntax error and why?" I'd vote to repopen in that case. — RBerteig, Sep 03 '10 at 20:52
This question is not a duplicate of the linked question. The linked question is about C#, which is a completely different language. — 12431234123412341234123, Sep 03 '21 at 08:35

score 25 · Accepted Answer · answered Sep 03 '10 at 18:15

25

 bool ispowerof2(unsigned int x) {
   return x && !(x & (x - 1));
 }

Note that the bit pattern of a power of two is of the form 10...0 and that of a number just one less is 011...1.

As far as your code is concerned:

for( i=0, flag=0, y=1;
     y<INT_MAX;      
     if(flag)break,if(flag)printf("YES"),if(y==x)flag=1,i++,y=pow(2,i)
   );

The last part of the for is illegal.

answered Sep 03 '10 at 18:15

dirkgently

108,024
16
131
187

Since he's using `int`s, wouldn't it be better to use them (and skip the special case for 0)? – James Curran Sep 03 '10 at 18:23
@James: This'd be an implicit conversion. I see no harm. But why should the special case be skipped? – dirkgently Sep 03 '10 at 18:27
@james:I dont find anything illegal in my code.I have followed all the rules. – Sep 03 '10 at 18:30
@dirk: because (0 & -1)==0. The special case is only needed in x-1 is illegal. – James Curran Sep 03 '10 at 18:54
@James Curran: You misunderstand the special case. `(0 & -1) == 0` is certainly true, but since 0 is *not* a power of two, "true" should not be returned in that case. This is true whether you use unsigned or signed values (and `x-1` with an unsigned `x == 0` is perfectly legal). – caf Sep 04 '10 at 03:38

score 8 · Answer 2 · answered Sep 03 '10 at 18:16

8

I'm not going to answer directly, but I'll note that a power of two has only one bit set, and when you subtract one from a number, it clears the least significant bit that's set, and sets all the less significant bits. Looking at one of these fact AND then the other might give an idea of how to detect the first condition in one line.

answered Sep 03 '10 at 18:16

Jerry Coffin

476,176
80
629
1,111

Did you mean to say `it clears the most significant bit that's set` – Cholthi Paul Ttiopic Sep 25 '18 at 06:57
1

@CholthiPaulTtiopic: No. It clears the least significant bit that's currently set. So given (for example) `0111000`, the least significant bit that's currently set is bit 3. If we subtract 1, bit 3 will be cleared, and bits 0 through 2 will be set (and all the higher bits remain unchanged), giving `0110111`. – Jerry Coffin Oct 07 '20 at 19:46

score 5 · Answer 3 · answered Sep 03 '10 at 18:32

5

Personally, I like this flavor better:

bool isPow2 = ((x & ~(x-1))==x)? x : 0;

It relies on the same binary math, but it handles the case of zero is not a power of 2 in a more subtle way.

answered Sep 03 '10 at 18:32

abelenky

63,815
23
109
159

score 1 · Answer 4 · answered Sep 03 '10 at 18:18

1

With the comma operator, the expressions are evaluated left to right, so your `if(flag)printf("YES") will never be executed.

I'm curious what the point of this is, as (val != 0) && ((val & val-1) == 0) returns non-zero if a value is a power of two.

answered Sep 03 '10 at 18:18

dash-tom-bang

17,383
5
46
62

Determine if an int is a power of 2 or not in a single line

4 Answers4

Linked