#include <iostream>
#include <limits>

// Printing an integer in binary
//
// We normally write integers in base 10.
//
// For example:
//
//     173
//
// means:
//
//          2        1        0
//     1*10  + 7*10  + 3*10.
//
// In binary, we use base 2 and therefore have only
// the digits:
//
//     0 and 1.
//
// For example:
//
//     13
//
// is written:
//
//     1101
//
// because:
//
//          3       2       1       0
//     1*2  + 1*2  + 0*2  + 1*2
//
//       = 8 + 4 + 0 + 1
//
//       = 13.
//
//
//
// How can we print an integer in binary without
// first storing all of its binary digits?
//
// Integer division and remainder give us a useful
// observation.
//
// Suppose:
//
//     n = 13.
//
// Then:
//
//     13/2 = 6
//
// and:
//
//     13%2 = 1.
//
// Thus:
//
//     binary(13)
//
// is:
//
//     binary(6)
//
// followed by:
//
//     1.
//
// Similarly:
//
//     6/2 = 3
//
// and:
//
//     6%2 = 0.
//
// Thus:
//
//     binary(6)
//
// is:
//
//     binary(3)
//
// followed by:
//
//     0.
//
// This gives us a recursive algorithm.
//
// To print n in binary:
//
//     1. Recursively print n/2.
//
//     2. Print n%2.
//
// The trivial cases are:
//
//     n = 0
//
// and:
//
//     n = 1.
//
//
//
// For negative integers, we first print:
//
//     -
//
// and then print the magnitude of the integer in
// binary.

// Function declarations
int main();

void print_binary(
    int const n
);

void print_binary_unsigned(
    unsigned int const n
);


// Function definitions
int main() {
    for ( int k{ -17 }; k <= 17; ++k ) {
        std::cout << k << "\t";
        print_binary( k );
        std::cout << std::endl;
    }


    // Test some additional values.

    std::cout << std::endl;

    std::cout << "42\t";
    print_binary( 42 );
    std::cout << std::endl;

    std::cout << "255\t";
    print_binary( 255 );
    std::cout << std::endl;

    std::cout << "256\t";
    print_binary( 256 );
    std::cout << std::endl;


    // There is one particularly interesting case:
    //
    //     the smallest possible int.
    //
    // On the usual 32-bit representation this is:
    //
    //     -2147483648.
    //
    // Its positive magnitude, 2147483648, cannot
    // itself be represented by a signed 32-bit int.
    //
    // Our implementation below is written so that
    // this case is handled correctly.

    int const smallest{
        std::numeric_limits<int>::min()
    };

    std::cout << smallest << "\t";
    print_binary( smallest );
    std::cout << std::endl;

    return 0;
}


// void print_binary( ... )
//
// @author    Douglas Wilhelm Harder
// @date      2020-11-01
// @version   2.0
//
// @param n
//     An integer to be printed in binary.
//
// @algorithm
//
// If n is negative:
//
//     1. Print a minus sign.
//
//     2. Determine the magnitude of n as an
//        unsigned integer.
//
//     3. Recursively print that magnitude.
//
// Otherwise:
//
//     Recursively print n as an unsigned integer.
//
// We use an unsigned integer for the magnitude
// because simply evaluating:
//
//     -n
//
// is not safe for every possible int.
//
// In particular, if:
//
//     n = INT_MIN,
//
// its positive magnitude may not be representable
// as an int.

void print_binary(
    int const n
) {
    if ( n < 0 ) {
        std::cout << "-";

        // Converting n to unsigned first gives its
        // representation modulo one more than the
        // maximum unsigned value.
        //
        // Subtracting that unsigned value from zero
        // therefore gives the magnitude without
        // attempting to calculate -n as a signed
        // integer.

        unsigned int const magnitude{
            0u - static_cast<unsigned int>( n )
        };

        print_binary_unsigned( magnitude );
    } else {
        print_binary_unsigned(
            static_cast<unsigned int>( n )
        );
    }
}


// void print_binary_unsigned( ... )
//
// @param n
//     A non-negative integer to be printed in
//     binary.
//
// @algorithm
//
// If n is 0 or 1, simply print n.
//
// Otherwise:
//
//     1. Recursively print n/2.
//
//     2. Print n%2.
//
// The recursive call removes the final binary digit.
//
// The remainder:
//
//     n%2
//
// is exactly that final binary digit.

void print_binary_unsigned(
    unsigned int const n
) {
    if ( n <= 1 ) {
        std::cout << n;
    } else {
        print_binary_unsigned( n/2 );
        std::cout << n%2;
    }
}














































// Understanding the recursion
//
// Consider:
//
//     print_binary( 13 ).
//
// Since 13 is positive, this calls:
//
//     print_binary_unsigned( 13 ).
//
// Since 13 > 1:
//
//     print_binary_unsigned( 13/2 );
//
// is called first.
//
// Since:
//
//     13/2 = 6,
//
// we now have:
//
//     print_binary_unsigned( 6 ).
//
//
//
// That calls:
//
//     print_binary_unsigned( 3 ),
//
// which calls:
//
//     print_binary_unsigned( 1 ).
//
//
//
// Thus, the recursive calls are:
//
//     print_binary_unsigned( 13 )
//
//         print_binary_unsigned( 6 )
//
//             print_binary_unsigned( 3 )
//
//                 print_binary_unsigned( 1 )
//
//
//
// At this point we reach the trivial case.
//
// The value:
//
//     1
//
// is printed.
//
// Thus, the output is currently:
//
//     1
//
//
//
// We now return to the call for 3.
//
// That call prints:
//
//     3%2
//
// which is:
//
//     1.
//
// The output is now:
//
//     11
//
//
//
// We return to the call for 6.
//
// It prints:
//
//     6%2
//
// which is:
//
//     0.
//
// The output is now:
//
//     110
//
//
//
// Finally, we return to the call for 13.
//
// It prints:
//
//     13%2
//
// which is:
//
//     1.
//
// The final output is:
//
//     1101.
//
//
//
// The call stack therefore behaves like:
//
//
//     Calls:
//
//         13
//          |
//          v
//          6
//          |
//          v
//          3
//          |
//          v
//          1
//
//
//     Returns:
//
//          1        prints 1
//          |
//          v
//          3        prints 1
//          |
//          v
//          6        prints 0
//          |
//          v
//         13        prints 1
//
//
//     Result:
//
//         1101
//
//
// This illustrates an important use of recursion.
//
// We discover the binary digits beginning with the
// LEAST significant digit:
//
//     13%2 = 1
//      6%2 = 0
//      3%2 = 1
//      1%2 = 1.
//
// That gives:
//
//     1, 0, 1, 1
//
// in the opposite order from how they must be
// printed.
//
// Recursion allows us to delay printing each digit
// until the recursive call returns.
//
// Consequently, the digits appear in the required
// order:
//
//     1, 1, 0, 1.
//
//
//
// Why does division by 2 remove a binary digit?
//
// Suppose the binary representation of n is:
//
//     abcde
//
// where each letter represents one binary digit.
//
// Dividing by 2 shifts all binary place values one
// position to the right.
//
// The final digit is discarded.
//
// Thus:
//
//     abcde / 2
//
// gives:
//
//     abcd.
//
// The remainder tells us what the discarded digit
// was:
//
//     n%2 = e.
//
// Therefore:
//
//     binary(n)
//
// is:
//
//     binary(n/2)
//
// followed by:
//
//     n%2.
//
// This is exactly what the recursive algorithm
// implements.
//
//
//
// Using bit operations
//
// For a non-negative integer:
//
//     n/2
//
// is equivalent to:
//
//     n >> 1.
//
// Also:
//
//     n%2
//
// is equivalent to:
//
//     n & 1.
//
// Therefore, the recursive step could instead be
// written:
//
//     print_binary_unsigned( n >> 1 );
//
//     std::cout << (n & 1);
//
// This works because binary representation is
// directly related to powers of two.
//
// However, the version:
//
//     n/2
//
// and:
//
//     n%2
//
// expresses the mathematical idea more directly.
//
// It also leads naturally to printing numbers in
// bases other than two.
//
//
//
// Printing in octal
//
// Octal is base 8.
//
// Therefore, instead of dividing by 2, divide by 8.
//
// Instead of taking the remainder modulo 2, take
// the remainder modulo 8.
//
// Thus:
//
//     print_octal( n/8 );
//
// followed by:
//
//     n%8
//
// gives the octal representation.
//
// The trivial case becomes:
//
//     n < 8.
//
//
//
// For example:
//
//     83/8 = 10 remainder 3
//
//     10/8 =  1 remainder 2.
//
// Therefore:
//
//     83
//
// in decimal is:
//
//     123
//
// in octal.
//
//
//
// Printing in hexadecimal
//
// Hexadecimal is base 16.
//
// The same idea works:
//
//     print_hexadecimal( n/16 );
//
// followed by the digit represented by:
//
//     n%16.
//
// There is one additional complication.
//
// The possible remainders are:
//
//     0, 1, 2, ..., 15.
//
// But hexadecimal digits are:
//
//     0 1 2 3 4 5 6 7 8 9 A B C D E F.
//
// Thus:
//
//     10 -> A
//     11 -> B
//     12 -> C
//     13 -> D
//     14 -> E
//     15 -> F.
//
//
//
// A more general observation
//
// Suppose we wanted to print a positive integer in
// base b.
//
// The same recursive idea is:
//
//     print_base( n/b, b );
//
// followed by:
//
//     print the digit n%b.
//
// The trivial case occurs when:
//
//     n < b.
//
// Thus, binary, octal, decimal, and hexadecimal
// are not fundamentally different algorithms.
//
// They are all instances of the same idea:
//
//     quotient  -> remaining digits
//
//     remainder -> final digit.
//
//
//
// What happens if we reverse the order?
//
// Our recursive step is:
//
//     print_binary_unsigned( n/2 );
//
//     std::cout << n%2;
//
// Suppose we reverse these:
//
//     std::cout << n%2;
//
//     print_binary_unsigned( n/2 );
//
// For:
//
//     n = 13,
//
// we would print:
//
//     1
//
// then recurse with 6.
//
// We would then print:
//
//     0
//
// then recurse with 3.
//
// Then:
//
//     1
//
// and finally:
//
//     1.
//
// The result would be:
//
//     1011.
//
// These are the binary digits of 13 in REVERSE
// order.
//
// Thus, whether an operation occurs:
//
//     before the recursive call
//
// or:
//
//     after the recursive call
//
// can fundamentally change the result.
//
//
//
// Compare with recursive insertion sort
//
// We just saw the same idea in recursive insertion
// sort.
//
// There:
//
//     insertion_sort(
//         array,
//         capacity - 1
//     );
//
// occurs BEFORE:
//
//     insert(
//         array,
//         capacity
//     );
//
// The work performed after the recursive call is
// delayed until the smaller problem has been
// solved.
//
// Here:
//
//     print_binary_unsigned( n/2 );
//
// occurs BEFORE:
//
//     std::cout << n%2;
//
// so printing the final digit is delayed until the
// more significant digits have been printed.
//
//
//
// Runtime
//
// Each recursive call divides n by 2:
//
//     n
//
//     n/2
//
//     n/4
//
//     n/8
//
//     ...
//
// until the value is 0 or 1.
//
// How many times can we divide n by 2?
//
// Approximately:
//
//     log_2(n)
//
// times.
//
// Therefore, for a positive n, the runtime is:
//
//     Theta(log(n)).
//
//
//
// This should look familiar.
//
// Earlier we studied the recurrence:
//
//     T(n) = T(n/2) + 1.
//
// That recurrence has the solution:
//
//     T(n) = Theta(log(n)).
//
// Our binary-printing function has exactly this
// recursive structure.
//
//
//
// There is also a more concrete interpretation.
//
// A positive integer n requires:
//
//     floor(log_2(n)) + 1
//
// binary digits.
//
// The function prints each of those digits exactly
// once.
//
// Thus, its runtime is proportional to the number
// of digits it prints.
//
//
//
// Stack space
//
// The maximum number of active recursive calls is
// also proportional to:
//
//     log_2(n).
//
// Therefore, the additional stack space is:
//
//     Theta(log(n)).
//
// This contrasts with recursive selection sort and
// recursive insertion sort, where the argument was
// reduced by one on each call:
//
//     n, n - 1, n - 2, ...
//
// giving:
//
//     Theta(n)
//
// recursive depth.
//
// Here we repeatedly DIVIDE the problem size:
//
//     n, n/2, n/4, ...
//
// giving:
//
//     Theta(log(n))
//
// recursive depth.
//
//
//
// A subtle problem with negative integers
//
// The original implementation might naturally be
// written:
//
//     if ( n < 0 ) {
//         std::cout << "-";
//         print_binary( -n );
//     }
//
// This works for almost every negative int.
//
// However, there is one exceptional value.
//
// Suppose int uses the common 32-bit range:
//
//     -2147483648
//
// through:
//
//      2147483647.
//
// Notice the asymmetry.
//
// The magnitude of:
//
//     -2147483648
//
// is:
//
//      2147483648.
//
// But that value is too large to store in an int.
//
// Therefore, attempting to calculate:
//
//     -n
//
// when:
//
//     n = -2147483648
//
// cannot produce a representable int value.
//
// In C++, signed integer overflow is undefined
// behavior.
//
// Our implementation avoids this by converting the
// negative value to unsigned and performing the
// negation using unsigned arithmetic.
//
//
//
// Why not print the machine representation?
//
// When we print:
//
//     -13
//
// this function prints:
//
//     -1101.
//
// That is the ordinary mathematical binary
// representation of negative thirteen.
//
// It is NOT printing the underlying bit pattern
// used by the computer to store the signed integer.
//
// On a typical modern computer using two's
// complement, the stored representation of -13
// would instead begin with many leading 1 bits.
//
// These are two different questions:
//
//     How do we WRITE the integer -13 in base 2?
//
// versus:
//
//     What bit pattern does the computer use to
//     STORE an int whose value is -13?
//
// This exercise answers the first question.
//
//
//
// Questions:
//
// 1. What is the binary representation of 13?
//
// 2. What are:
//
//        13/2
//
//    and:
//
//        13%2?
//
// 3. Why does dividing by 2 remove the final
//    binary digit?
//
// 4. Why does n%2 give the final binary digit?
//
// 5. What is the trivial case in
//    print_binary_unsigned()?
//
// 6. Write the complete sequence of recursive
//    calls made by:
//
//        print_binary( 13 ).
//
// 7. In what order are the binary digits discovered?
//
// 8. In what order are they printed?
//
// 9. Why must the recursive call occur BEFORE
//    printing n%2?
//
// 10. What would be printed if those two statements
//     were reversed?
//
// 11. How would you modify the algorithm to print
//     an integer in octal?
//
// 12. How would you modify it to print an integer
//     in hexadecimal?
//
// 13. Why does hexadecimal require additional work
//     when the remainder is between 10 and 15?
//
// 14. Describe a recursive algorithm for printing
//     an integer in an arbitrary base b.
//
// 15. What recurrence describes the runtime of
//     print_binary_unsigned()?
//
// 16. Why is the runtime:
//
//        Theta(log(n))?
//
// 17. Why is the recursion depth also:
//
//        Theta(log(n))?
//
// 18. Why is:
//
//        print_binary( -n )
//
//     potentially unsafe when n is the smallest
//     representable int?
//
// 19. What is the difference between printing:
//
//        -1101
//
//     and printing the actual machine bit pattern
//     used to represent -13?
//
//
//
// The central recursive idea in this example is:
//
//     If I knew how to print all but the final
//     digit, how could I print the entire number?
//
// The answer is:
//
//     Recursively print the quotient.
//
//     Then print the remainder.
//
// More generally:
//
//     quotient  -> smaller version of the problem
//
//     remainder -> information needed to finish
//                  the current problem.
//
// This pattern appears in many recursive algorithms
// involving representations of integers.