Guest pipplo Posted November 7, 2003 Report Share Posted November 7, 2003 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 Quote Link to comment Share on other sites More sharing options...
fuzzylizard Posted November 7, 2003 Report Share Posted November 7, 2003 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); } Quote Link to comment Share on other sites More sharing options...
Guest pipplo Posted November 7, 2003 Report Share Posted November 7, 2003 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. Quote Link to comment Share on other sites More sharing options...
willisoften Posted November 7, 2003 Report Share Posted November 7, 2003 (edited) 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 November 7, 2003 by willisoften Quote Link to comment Share on other sites More sharing options...
johnnyv Posted November 7, 2003 Report Share Posted November 7, 2003 (edited) 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 November 7, 2003 by johnnyv Quote Link to comment Share on other sites More sharing options...
johnnyv Posted November 7, 2003 Report Share Posted November 7, 2003 (edited) 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 November 7, 2003 by johnnyv Quote Link to comment Share on other sites More sharing options...
Guest pipplo Posted November 7, 2003 Report Share Posted November 7, 2003 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 Quote Link to comment Share on other sites More sharing options...
Guest pipplo Posted November 7, 2003 Report Share Posted November 7, 2003 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? Quote Link to comment Share on other sites More sharing options...
Cannonfodder Posted November 7, 2003 Report Share Posted November 7, 2003 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? Quote Link to comment Share on other sites More sharing options...
Guest pipplo Posted November 7, 2003 Report Share Posted November 7, 2003 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! Quote Link to comment Share on other sites More sharing options...
baudolino Posted November 7, 2003 Report Share Posted November 7, 2003 (edited) 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 November 7, 2003 by baudolino Quote Link to comment Share on other sites More sharing options...
Guest daxxi Posted April 11, 2009 Report Share Posted April 11, 2009 (edited) 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 April 11, 2009 by daxxi Quote Link to comment Share on other sites More sharing options...
Cannonfodder Posted April 12, 2009 Report Share Posted April 12, 2009 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.. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
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.