#include <cstdint>
#include <iostream>

/***************************************************
 * Testing whether an integer is a power of two
 *
 * Write a function that determines whether a
 * positive integer n is a power of two.
 *
 * The powers of two are
 *
 *     1, 2, 4, 8, 16, 32, 64, ...
 *
 * Their binary representations have an important
 * property: exactly one bit is equal to 1.
 *
 * For example,
 *
 *      1 = 00000001
 *      2 = 00000010
 *      4 = 00000100
 *      8 = 00001000
 *     16 = 00010000
 *     32 = 00100000
 *
 *
 * SUBTRACTING ONE
 *
 * Suppose n is a power of two. Its binary
 * representation has the form
 *
 *     n     = ...01000...000
 *
 * where there is exactly one 1 bit.
 *
 * Subtracting 1 gives
 *
 *     n - 1 = ...00111...111.
 *
 * The single 1 bit in n becomes 0, while all bits
 * to its right become 1.
 *
 * For example,
 *
 *      8     = 00001000
 *      8 - 1 = 00000111
 *
 * Consequently,
 *
 *       00001000
 *     & 00000111
 *       --------
 *       00000000.
 *
 * Thus, if n is a power of two,
 *
 *     n & (n - 1)
 *
 * is zero.
 *
 *
 * WHAT IF n IS NOT A POWER OF TWO?
 *
 * If n is nonzero and is not a power of two, its
 * binary representation contains at least two
 * 1 bits.
 *
 * For example,
 *
 *     12     = 00001100
 *     12 - 1 = 00001011
 *
 * and therefore
 *
 *       00001100
 *     & 00001011
 *       --------
 *       00001000.
 *
 * At least one 1 bit remains common to n and n - 1,
 * so the result is not zero.
 *
 *
 * THE SPECIAL CASE n == 0
 *
 * Zero is not a power of two.
 *
 * We therefore test
 *
 *     n != 0
 *
 * before applying the bitwise test.
 *
 * Thus, n is a power of two exactly when
 *
 *     (n != 0) && ((n & (n - 1)) == 0).
 ***************************************************/

// Function declarations
int main();
bool is_power_of_two( std::uint64_t n );

// Function definitions
int main() {
    for ( std::uint64_t k{ 0 }; k < 1025; ++k ) {
        if ( is_power_of_two( k ) ) {
            std::cout << k << std::endl;
        }
    }

    return 0;
}

/***************************************************
 * is_power_of_two
 *
 * Returns true if n is a power of two and false
 * otherwise.
 ***************************************************/
bool is_power_of_two( std::uint64_t n ) {
    return (n != 0) && ((n & (n - 1)) == 0);
}


/***************************************************
 * C++20 and later
 *
 * You are not expected to use this in this exercise,
 * but the C++ standard library now provides this
 * operation.
 *
 * If <bit> is included, we can write
 *
 *     std::has_single_bit( n )
 *
 * to determine whether an unsigned integer contains
 * exactly one 1 bit. Thus,
 *
 *     std::has_single_bit( n )
 *
 * performs the test we implemented above.
 *
 * The standard library also provides several other
 * useful bit-manipulation functions in <bit>.
 ***************************************************/