 # C: Test for power of two

## Recommended Posts I was looking through this 'prepare for an interview' booklet and I came across this example question. I'm at a loss here..

Give a 'simple' C expression to test whether or not a number is a power of two. No loops may be used.

Could y'all help at all? Thanks

##### Share on other sites

Not sure about an expression, but here is a very simple function

```int powOf2(int n) {
if (n == 2)
return 1;
powOf2(n/2);
}```

You should even be able to simplify that farther

```int powOf2(int n) {
return (powOf2(n/2) == 2);
}```

##### Share on other sites Yeah, i can do it using a function, but I can't think of an 'expression'... It's a really vague question too cause I don't know if you could use standard math.h functions either....

one thing i was thinking is this

if ( frexp(num, tmpOut) == 1 )

cause that would mean the mantissa is a 1, and the number is a power of 2, but the problem is that requirement for tmpOut.. :-/ I dunn.

##### Share on other sites
I was looking through this 'prepare for an interview' booklet and I came across this example question.  I'm at a loss here..

Give a 'simple' C expression to test whether or not a number is a power of two. No loops may be used.

Could y'all help at all?  Thanks

I think but I'm not sure that your looking for remainders or modulus

2%2 =0

8 %2= 0 and 8 is a power of 2

This falls down with numbers like 6

6 %2 = 0 but 6 is not a power of two.

I think that if x / 2 = a and a % 2 = 0 its a power of 2

As far as I can tell:This is the same as if log (base 2) of x = integer

log 2 of 8 is 3

log 2 of 64 is 64 is 6

log 2 of 256 is 8

but log 2 of 6 is 2.584...

I'm pretty sure there are methods for logs and checking if a number is an integer within C but i don't know how to use them so I'd go with

if x / 2 = a and a % 2 = 0 its a power of 2 (not sure how to code it)

something like:

Set up yor variables

```if ((a =(x /2)) && (a % 2==0))
printf ("power of 2");
else
printf("not a power of 2);```

I've been celebrating so if this is plain wrong feel free to ask the mods to remove it. BUT Hope I've been of some help!

Edited by willisoften

##### Share on other sites

basically what you want to do is for a given value of x calculate the (log(x)/log(2)) and see if its a whole number greater than or equal to 1.

double x = 64;

double y = (log(x)/log(2));

y = 6

the function log2(double x) is equivalent to (log(x)/log(2)) supposedly

There must be a fuction to see if a double is not a whole number but i don't know it all i can think of is making an int the value of the double then dividing them and seeing if it equals 1

int z = y;

if((y/z) != 1)

{

/* the double y is not a whole number! */

}

Edited by johnnyv

##### Share on other sites

Will had the idea but in c the log fuctions don't work with ints and you can't get the modulus of a double division only an int division AFAIK.

this function returns 0 if the number is not a power of 2 and it's power if it is.

There must be an existing function for this sort of thing (i really know bugger all about c and c++).

```#include <math.h>
#include <stdio.h>

int power_of2(double x)
{
double y = (log(x)/log(2));
int z = y;
if((y/z) != 1)
{
return 0;
}
else
{
return z;
}
}

int main()
{
double a=45;
double b=64;

printf("%.f is 2^%d \n",a,power_of2(a));
printf("%.f is 2^%d \n",b,power_of2(b));

return 0;
}```

Edited by johnnyv

##### Share on other sites I was looking through this 'prepare for an interview' booklet and I came across this example question.  I'm at a loss here..

Give a 'simple' C expression to test whether or not a number is a power of two. No loops may be used.

Could y'all help at all?  Thanks

I think but I'm not sure that your looking for remainders or modulus

2%2 =0

8 %2= 0 and 8 is a power of 2

This falls down with numbers like 6

6 %2 = 0 but 6 is not a power of two.

I think that if x / 2 = a and a % 2 = 0 its a power of 2

As far as I can tell:This is the same as if log (base 2) of x = integer

log 2 of 8 is 3

log 2 of 64 is 64 is 6

log 2 of 256 is 8

but log 2 of 6 is 2.584...

I'm pretty sure there are methods for logs and checking if a number is an integer within C but i don't know how to use them so I'd go with

if x / 2 = a and a % 2 = 0 its a power of 2 (not sure how to code it)

something like:

Set up yor variables

```if ((a =(x /2)) && (a % 2==0))
printf ("power of 2");
else
printf("not a power of 2);```

I've been celebrating so if this is plain wrong feel free to ask the mods to remove it. BUT Hope I've been of some help!

I don't think it works on 2, cause 2/2 is 1, then 1 % 2 is 1... :-/

Then it also wouldn't work on...640...

640 / 2 = 320

320 % 2= 0

:-/

what the hell company would ask THAT in an interview! ughh

I give up, the question is just too vague

Thanks for all the help guys

##### Share on other sites Will had the idea but in c the log fuctions don't work with ints and you can't get the modulus of a double division only an int division AFAIK.

this function returns 0 if the number is not a power of 2 and it's power if it is.

There must be an existing function for this sort of thing (i really know bugger all about c and c++).

`<!--QuoteEBegin-->#include <math.h><!--QuoteEBegin-->#include <stdio.h><!--QuoteEBegin--><!--QuoteEBegin-->int power_of2(double x)<!--QuoteEBegin-->{<!--QuoteEBegin-->double y = (log(x)/log(2));<!--QuoteEBegin-->int z = y;<!--QuoteEBegin-->	if((y/z) != 1)<!--QuoteEBegin-->	{<!--QuoteEBegin-->	return 0;<!--QuoteEBegin-->	}<!--QuoteEBegin-->	else<!--QuoteEBegin-->	{<!--QuoteEBegin-->	return z;<!--QuoteEBegin-->	}<!--QuoteEBegin-->}<!--QuoteEBegin--><!--QuoteEBegin-->int main()<!--QuoteEBegin-->{<!--QuoteEBegin-->double a=45;<!--QuoteEBegin-->double b=64;<!--QuoteEBegin--><!--QuoteEBegin-->printf("%.f is 2^%d \n",a,power_of2(a));<!--QuoteEBegin-->printf("%.f is 2^%d \n",b,power_of2(b));<!--QuoteEBegin--><!--QuoteEBegin-->return 0;<!--QuoteEBegin-->}<!--QuoteEBegin-->`

Based on this it seems in C++ you could do

if ( ( log(num)/log(2) ) / ( (int) ( log(num)/log(2) ) ) ) == 1 ) {

}

hehe, but is that simple?

##### Share on other sites

bit logic?

2 - 0000 0010

4 - 0000 0100

8 - 0000 1000

so on, always has one 1 in the expression..

So maybe you can figure some kind of bit comparison to validate that in an expression?

##### Share on other sites Amazing! A friend came up with a very elegant idea. I knew it had something to do with the fact that a power of two has only a signe 1 int he bits. Heres what you do

if ( ((n | (n - 1)) + 1) / 2 == n ) {

cout << "This is a power of two" << endl;

}

This is amazing it seems so simple now that i think about it.

n | n-1 basically fills up everything below the power with 1's if it is a power of two, so then by adding one, you are essentially multiplying n by 2. So if you divide that by two you shoudl get n. For example

01000 - n

00111 - (n-1)

-------

01111 n | (n-1)

00001

-------

10000

divide by two gives you

01000 = n!

amazing!

##### Share on other sites

assuming that you work with 5 bits unsigned integers, pipplo's idea does not identify 10000, because of the arithmetic overflow.

another idea is to use the C constant UINT_MAX (which give the maximal unsigned integer value) like this

n unsigned int;

if ( (UINT_MAX - n) +1 == n) then UINT_MAX is defined in limits.h

Edited by baudolino

##### Share on other sites Amazing! A friend came up with a very elegant idea. I knew it had something to do with the fact that a power of two has only a signe 1 int he bits. Heres what you do

if ( ((n | (n - 1)) + 1) / 2 == n ) {

cout << "This is a power of two" << endl;

}

This is amazing it seems so simple now that i think about it.

n | n-1 basically fills up everything below the power with 1's if it is a power of two, so then by adding one, you are essentially multiplying n by 2. So if you divide that by two you shoudl get n. For example

01000 - n

00111 - (n-1)

-------

01111 n | (n-1)

00001

-------

10000

divide by two gives you

01000 = n!

amazing!

Thanks, I found this thread by the usual method. :)

There's an even more amazing test that's, essentially, the same as your friend's ...

`		  !(n & n-1)` ```#include <stdio.h>

int main()
{
int n;

for (n = 1; n < 1000000; n++) {
if ( (n & n-1) ) {
/* not a power of 2 */
}
else {
printf("%6d   0x%05X\n", n, n);
}
}
getchar(); /* press any key ... */
}

/*
1   0x00001
2   0x00002
4   0x00004
8   0x00008
16   0x00010
32   0x00020
64   0x00040
128   0x00080
256   0x00100
512   0x00200
1024   0x00400
2048   0x00800
4096   0x01000
8192   0x02000
16384   0x04000
32768   0x08000
65536   0x10000
131072   0x20000
262144   0x40000
524288   0x80000
*/

/* Preprocessor example */
#define POW_TWO  8
#if (POW_TWO & POW_TWO-1)
# error --->  POW_TWO must be a power of 2  <---
#endif```

It's probably a bit late for the original need, though. ;)

Edited by daxxi

##### Share on other sites

We will just have to vote this longest running thread in MUB.. although it is nice to finally have an answer to this question.. its been keeping me up at nights..

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.