Saturday, 6 September 2014

Given number is a power of 2 or not

To check whether a given number is power of 2 or not

Algorithm
To check whether a given number, n  is power of 2 or not we do bit AND of n and n-1. It will be zero if number is power of 2. 
Eg: if n is 16 (10000) and n-1 is 15(01111), then n&n-1 is 0. Bit NOT of zero is 1. 
Logical AND of n and 1 will be 1. We cant just use ! ( n&n-1 )because for n=0, it will 1. But 0 is not power of 2.

Input:       number.
Output:    n is (not)power of 2

#include <iostream>
using namespace std;
int PowerOfTwo ( int n )
{
    return ( n &&! ( n&n-1 ) );
}
int main()
{
    int n;
    cin>>n;
    if ( PowerOfTwo ( n ) )
    {
        cout<<n<<" is power of 2";
    }
    else {
        cout<<n<<" is not power of 2";
    }
    return 0;
}


Please comment if you find anything incorrect

No comments:

Post a Comment