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;

}