Interview Questions And Answers 
-
Give a one-line C expression to test whether a number is a power of 2. Now implement it without using loops.
11,172 Views |
(8 votes, avg: 3.75)
Loading ...
Answers »
Our Sponsors
Our Sponsors
if (x ^ (x-1) == 0 then its a power of 2
This works for zero also:
if (x && ~(x & (x-1)) == 0)
I don’t think that Ashley’s plan will work.
(X ^ (X-1)) will never equal 0 for a positive integer
1^0 = 1
2^1 = 2
3^2 = 9
etc..
if ((x && (xx-1)) == 0) {} //x is power of 2
this will work i suppose (assuming x!= 0)
if( ~(x^(x-1))== 0) then it is power of 2
(^ :exclusive or)
have you tried this solutions in a loop ?
they don’t seem to work, but inspired on them, this does:
(x ^(x-1))-x > 0
will be 1 (true) for all powers of 2 including 0.
ALL THE ABOVE ARE WRONG
THE CORRECT ONE IS
if(!(x&(x-1)))
maxPower2 = (~0 >>> 1) + 1
if (0 == (maxPower2 % x)) then x is power 2
My previous post probably is not clear.
(2^n % x) == 0 only if x is power 2
Maximum 2^n = ((unsigned)~0 >> 1) + 1 ==
1000000..0
if (0 == (((unsigned)~0 >> 1) + 1) % x)) then x is power 2
. The binary representation of any integer number except 0 will contain at least a bit 1. Taking into account this property we can represent a number like this:
X = b1b2 .bk10 0t
Note: the number t of trailing zeros can be zero and also the number k of leading bits can be zero.
Let first assume that X is an unsigned integer. Then if the number is not a power of two at least one bit from (bi) sequence must be 1. If we represent in binary form the number X-1 we get:
X-1 = b1b2 .bk01 1t
Looking at these form it is obvious that X & (X-1) = b1b2 .bk001 0t . Only for a power a power of two bi=0, for each i so we have X & (X-1) = 0 only for a power of two.
The macro to test the number can be: #define pow2(X) (!(X&(X-1)))
For X = b1b2 .bk101 0t then X=c1c2 .ck10 0t where ci=1-bi (the negative number is represent as the complement of 2). For a power of two ci=1, for each i and it is difficult to test it so for a negative number it easier to test its absolute value. The macro will be extented like this: #define pow2(X) (X>0)?(!((X)&(X-1))): (!((-X)&(-X-1)))
Let take now a closer view for the case X=0. This case was excluded at the beginning when we assumed we had at least on bit 1. 0 cant be a power of two so the macro will be extented again to take care of 0.
#define pow2(X) (X!=0 && ((X>0)?(!((X)&(X-1))): (!((-X)&(-X-1)))))
Try this out :
if( (N !=0) && ((2*N-1) ^ (N <<1)) == ((2*N-1)
#include<stdio.h>
#include<conio.h>
void main()
{
unsigned int x;
int base,j;
clrscr();
//Program to clear MSB of the number
printf(”nEnter value of x = “);
scanf(”%u”,&x);
x=x&(0×7fff);
printf(”nNew value of x = %u”,x);
//Program for testing whether a no. is power of 2
printf(”nEnter value of x = “);
scanf(”%u”,&x);
if(x&x-1)
printf(”nNumber is not power of 2 “);
else
printf(”nNumber is power of 2 “);
//Program to find discrete log of the number;
printf(”nEnter the number = “);
scanf(”%u”,&x);
printf(”nEnter the base = “);
scanf(”%u”,&base);
j=1;
while(x>=base)
{
x=x/base;
j++;
}
printf(”nLog x = %u”,j-1);
// Reversing bits of the number
printf(”nEnter the number = “);
scanf(”%u”,&x);
getch();
}
#include <stdio.h>
main(){
int num;
printf(” Enter number :”);
scanf(”%d”,&num);
if(!(num & (num-1)))
printf(”Power”);
else
printf(”Not power”);
}
if((log(number)/log(2))%2==0)
{
power of 2;
}
else
{
not;
}
smnaha’s solution is not correct
my solution is alomst same as Ashley’s
if((x&(x-1))==0)
if x is power of 2 it will have only 1 bit on at the location n , where x = 2 pow n
n-1 will have bits 0 to n-1 on and rest will be off
so bitwise and(&) of x , x-1 should be 0 only if x is a power of 2.
Ashley’s using XOR instead of AND which is also correct.
bool pof2(unsigned x)
{
return (x && (x & (x-1)) == 0) ;
}
I think all the answers here are either wrong completly, partially, or too complex. The best answer so far, by jinaljhaveri, was if(!(x&(x-1))), which I beleive works for all powers of 2, but also for 0, which is not a power of 2.
Basiclly, an integer which is the power of 2 will have one and only one bit set in its binary representation. If you subtract 1 from that, you will get all bits set (equal to 1) before the original 1 bit, and the rest are 0. Taking advantage of this, the answer is
if ((x << 1) == 1 + (x
it also cud be without using any bitwise operators
if(x!=0 && ((x/2)%2)==0)
printf(”x is a power of 2″);
sorry the above one misses something
if(x!=0 && ((x/2)%2)==0 && (x%2)==0)
printf(”x is a power of 2″);
In response to answer posted by rituvarm,
Even 12 is a power of 2 according to your equation?
To solve w/o bitwise operators
while(x%2==0 && (x/=2)!=1 && x!=0);
return(!(x-1));
returns true if x is a power of 2
else returns false
considers 0 not to be a power of 2.
yes u are rite..
mistake!
but u cant usea loop nish…u used awhile loop
cud u tell me without usinga loop please..
thnks
vadim, jinaljhaveri, octav_timofte
I do not think you have the correct answers.
This is what you are all basing your solutions on:
Some form of: X&(X-1)
This falls apart for any number that is the sum of two powers of two (e.g. (4+2)=6 ).
Example:
X = 6
X & (X-1) ==> 6&(6-1) ==> 6&5 != 0
According to your solutions, 6 would be a power of two. Keep trying guys!
KRogoway (myself) is a dorkus. Your solutions are correct, my check was incorrect.
Sorry guys.
First Solution
————-
int PowerofTwo(int x)
{
return ((x^(x-1)) == 2*x-1) ;
}
Second Solution
—————
int PowerofTwo(int x)
{
return (!(x&(x-1))) ;
}
Regards
if the no is power of 2 then only MSB will be 1 when converted to binary….
2=10
4=100…
so do a left shift on this no and if it becomes 0 dfntly thats power of 2….
if ( n
for the above soln. the variable should be stored in such a way that it is provided with just the amount of memory it is required .. not more..
only in that case one left shift will do the job….
else if ( ~(x^(x-1))) == 0) will be fine
Take the log of the number and Check whether the result in an integer or not.
Cheap solution.
And the number to be tested with the a number that is one less than that number. By properties of bitvectors the result should be 0.
The answer works for 0 also because in 2’s complement -1 is represented as 1111……….
Whats wrong with this logic if x is positive:
if ~(x-1) = 0, then x is a power of two
int result = ((x&(x-1))==0&&x)?1:0;
Just one line. result = 1 means True,result = 1 means False…
if the number is x then,
if ( (x & (x-1)) == 0)
{
its a power of 2
}
left shift by one, (BITWISE) and compare to 0, if true, power of 2!
Easy soln
Every pow of two number is a nth shift of 1,
1= 1 if ((n | (n - 1)) + 1 == 2 * n) -> n is pow of 2
Leave an Answer/Comment