# Powers of 2

``````/**
* @return true when n is a power of 2 and false otherwise.
*
* Discussion:
*
* A number is a power of two if only a single bit is set to 1. So check if
* the int n only has one bit!
*/

/*
The Algorithm:
- A number that is a power 2 by definition must be able to divide
by 2 indefinitely to one.
- Alternatively, a power of two must some instance in
```while (pow(2, i++) == num)``` and once it exceeds the
number it cannot work.
*/

bool solution1(int n)
{
double n2 = abs(double(n));

if (n == 0) return false;
else if (n == 1) return true;

while (n2 != 1) {
n2 /= 2;
if (n2 != int(n2))
return false;
}
return true;
}

/*
The Algorithm:
- Lets perform a bit of math: if n is a power of 2
then we can define that n = 2^k, when k constant
integer.

Then:

log_2(n) = log_2(2^k)
log_2(n) = k

return k == integer.
*/

bool solution2(int n)
{
if (n == 0)
return false;

n = abs(n);
double k = log2(n);
return (k == int(k));
}

/*
The Algorithm:
- Another way of looking at the problem is through bit manipulation.
- We know the following:
8 4 2 1
0 0 0 0

- That is, each bit in the number prepresents some power of 2, and some permutation
of those numbers can produce any kind of number.
- Since the powers of two are sequential (it doesn't skip any other powers of 2), if
must mean a power of 2 must contain a single bit.
*/
bool solution3(int n)
{
if (n == 0) return false;
int count = 0;
for (int i = 0; i < 32; i++) {
if (n & 1)
count++;
n >>= 1;
if (count > 1)
return false;
}
return true;
}

/*
The Algorithm:
- The best of the best. If we know that a power
of two always contain only 1 set bit, which is therefore
also its msb, then

1 0 0 0 0 0 = n
0 1 1 1 1 1 = n - 1

so any positive number (discluding the 2's complement bit)
will always be zeroed out if we so n & ( n - 1 ).
*/
bool solution4(int n)
{
n = abs(n);
return (n & (n - 1)) == 0;
}

int main()
{
// solution 1
for (int i = 0; i < 10; i++)
cout << boolalpha << solution1(i) << ' ';
cout << endl;

for (int i = 0; i < 10; i++)
cout << boolalpha << solution1(pow(2, i)) << ' ';
cout << endl << endl;

// solution 2
for (int i = 0; i < 10; i++)
cout << boolalpha << solution2(i) << ' ';
cout << endl;

for (int i = 0; i < 10; i++)
cout << boolalpha << solution2(pow(2, i)) << ' ';
cout << endl << endl;

// solution 3
for (int i = 0; i < 10; i++)
cout << boolalpha << solution3(i) << ' ';
cout << endl;

for (int i = 0; i < 10; i++)
cout << boolalpha << solution3(pow(2, i)) << ' ';
cout << endl << endl;

// solution 4
for (int i = 0; i < 10; i++)
cout << boolalpha << solution4(i) << ' ';
cout << endl;

for (int i = 0; i < 10; i++)
cout << boolalpha << solution4(pow(2, i)) << ' ';
cout << endl << endl;

}``````

Last updated