power of 2
Write a program to find if the given number n is a power of 2 or not?
posted by Rahul at 7:09 PM
Sunday, February 25, 2007
Contributors
Previous Posts
- Tech Samachar
- find unique element
- would-be entrepreneur's resignation mean failure o...
- In case you have missed
- Shortcut example
- Why Google so good in searching
- The Problem with Programming by Bjarne Stroustrup
- Interest Group
- Making hay while dotcom shines
- My standard problem
7 Comments:
do logical AND between number and its 1's complement
this may not work
come on guys. Put on your thinking caps.
it was a mistake from me.
answer :
number n then
if ((n&(n-1)== 0)
//is a power of 2
else
//not a power of 2
This logic will definitely work....
int count;
unsigned long long int v = 12;
count = (((v * 0x8000400020001ULL) & 0x8888888888888888ULL) >>3)% 0xf;
if ( 1 == count )
printf( " Power of 2 \n " );
else
printf ( " Not a power of 2 \n " );
Hey Satish, can you please explain the solution in a little more detail. Those huge numbers flew over my head.
I was doing some RnD on the bits manipulation, the result of that RnD is the above one line solution to find whether the given number is power of 2 or not.
Following is the brief explanation to the solution,
To expand a 16 bit value out and skew it 4 times we do
v * 0x8000400020001
To select every 4th bit we use
(v * 0x8000400020001) & 0x8888 8888 8888 8888
Finally we normalize it by bit shifting it 3 places right.
((v * 0x8000400020001) & 0x8888 8888 8888 8888) >> 3
And finally we count the number of bits by taking our modulus
count = (((v * 0x8000400020001) & 0x8888 8888 8888 8888) >> 3) %0xf
Actually we don't need such a large magic numbers to find the solution.
The following is the simple solution to the problem,
bool isPow2 = x && !( (x-1) & x );
Brief explanation:
If x is a power of two, it doesn't have any bits in common with x-1, since it
consists of a single bit on. Any positive power of two is a single bit on in its binary representation.
This means that we test if x-1 and x doesn't share bits with the and operator.
If x is zero (not a power of two) this doesn't hold, so we add an
explicit test for zero with xx && expression.
Fine Rahul...
Post a Comment
<< Home