Google Interview Question
Software EngineersCountry: Switzerland
I found this solution in the book "Cracking the code interview 5ed" chapter 5 Bit manipulation
((n & (n-1)) == 0)
Simple solution counting the number of bits set:
private static boolean slow(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1) {
count++;
}
n >>= 1;
}
return count == 1;
}
Better solution exploiting the properties of two's complement representation of and integer:
private static boolean fast(int n) {
return ((n & -n) == n);
}
void powOf2(int i)
{
int x =1;
while(x<i)
x = x*2;
if(x==i)
cout << "\n power of 2";
else
cout << "\n not power of 2";
return;
}
be sure to check that n > 0 since negative numbers aren't powers of 2
- SK July 14, 2015