Jump to content
Sign in to follow this  
Guest pipplo

C: Test for power of two

Recommended Posts

Guest pipplo

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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest pipplo

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest pipplo
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 this post


Link to post
Share on other sites
Guest pipplo
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest pipplo

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 this post


Link to post
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 :wall:

 

UINT_MAX is defined in limits.h

Edited by baudolino

Share this post


Link to post
Share on other sites
Guest daxxi
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)

 

:thumbs:

 

#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 this post


Link to post
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..

Share this post


Link to post
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
Sign in to follow this  

×
×
  • Create New...