Monday, 15 October 2012

power of 2 in constant time

Checking if number can be presented in power of 2 in constant time:


Algorithm

Number which can be represented in power of 2 its binary form will have 1 only at msb while
number one less than it will have 0 at msb while all other will have 1.
For examble
64=1000000
63=0111111
Now if we multiply each bit of 64 with corresponding bit of 63 we will get 0

SOURCECODE
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int m=64;
int n=63;
if((m&n)==0)//bitwise operator
cout<<"yes number can be represented in power of two";
else
cout<<"cannot be represented in power of two";
getch();
}

No comments:

Post a Comment