#include <iostream>

// Given a real number 'x':
//
//     floor(x)
//
// is the largest integer less than or equal to x,
// while
//
//     ceil(x)
//
// is the smallest integer greater than or equal to x.
//
// For example,
//
//       x       floor(x)    ceil(x)
//     ------------------------------
//      2.1          2          3
//      2.9          2          3
//      3.0          3          3
//      3.1          3          4
//      4.0          4          4
//      4.9          4          5
//       pi          3          4
//     -1.5         -2         -1
//
// Given a positive real number 'x', lg(x) denotes
// the base-2 logarithm of x. That is,
//
//          lg(x)
//     x = 2.
//
// For example,
//
//        lg(1) =  0
//        lg(2) =  1
//        lg(4) =  2
//        lg(8) =  3
//     lg(1024) = 10.
//
// For positive integers 'n' that are not powers of
// two, lg(n) is not an integer.
//
// Given a positive integer 'n', calculate the two
// integer values
//
//     floor(lg(n)) + 1
//
// and
//
//     ceil(lg(n + 1)).
//
// Do not use any mathematical library functions to
// calculate logarithms, floors, ceilings, or powers.
//
// What do you notice about these two values?

// Function declarations
int main();

// Function definitions
int main() {
    int n{};

    std::cout << "Enter a positive integer 'n': ";
    std::cin  >> n;

    if ( n <= 0 ) {
        return 0;
    }

    std::cout << "floor(lg(" << n
              << ")) + 1 = " << n << std::endl;

    std::cout << "ceil(lg(" << (n + 1)
              << ")) = " << n << std::endl;

    return 0;
}

























// Hint:
//
// Calculate the two values separately. We will start
// with
//
//     floor(lg(n)).
//
// If you wanted to calculate floor(lg(17)), consider
// the following powers of 2:
//
//                    k
//         k         2
//      ----------------
//         0          1
//         1          2
//         2          4
//         3          8
//         4         16
//         5         32
//
// We have
//
//     2^4 <= 17 < 2^5,
//
// so
//
//     floor(lg(17)) = 4.
//
// Similarly,
//
//     2^4 <= 16 < 2^5,
//
// so
//
//     floor(lg(16)) = 4,
//
// while
//
//     2^3 <= 15 < 2^4,
//
// so
//
//     floor(lg(15)) = 3.
//
// Start with two variables:
//
//     int k{ 0 };
//     int two_to_k{ 1 };
//
// Repeatedly:
//
//     1. increase 'k' by one, and
//     2. double 'two_to_k'
//
// while doubling 'two_to_k' would still produce a
// value less than or equal to n.
//
// Be careful: directly calculating
//
//     2*two_to_k
//
// could eventually overflow. Since n is positive,
// can you write an equivalent condition using n/2?

























// Next, calculate
//
//     ceil(lg(n + 1)).
//
// Again, consider powers of 2.
//
// If n == 16, then n + 1 == 17. Since
//
//     2^4 < 17 <= 2^5,
//
// we have
//
//     ceil(lg(16 + 1)) = 5.
//
// If n == 15, then n + 1 == 16. Since
//
//     2^4 = 16,
//
// we have
//
//     ceil(lg(15 + 1)) = 4.
//
// If n == 14, then n + 1 == 15. Since
//
//     2^3 < 15 < 2^4,
//
// we have
//
//     ceil(lg(14 + 1)) = 4.
//
// Start again with
//
//     int k{ 0 };
//     int two_to_k{ 1 };
//
// Repeatedly:
//
//     1. increase 'k' by one, and
//     2. double 'two_to_k'
//
// until
//
//     two_to_k > n.
//
// Why is this equivalent to finding
//
//     ceil(lg(n + 1))?

























// Here is one solution:
/*
int main() {
    int n{};

    std::cout << "Enter a positive integer 'n': ";
    std::cin  >> n;

    if ( n <= 0 ) {
        return 0;
    }

    int k{ 0 };
    int two_to_k{ 1 };

    // Calculate floor(lg(n)).
    while ( two_to_k <= n/2 ) {
        ++k;
        two_to_k *= 2;
    }

    std::cout << "floor(lg(" << n
              << ")) + 1 = " << (k + 1)
              << std::endl;

    k = 0;
    two_to_k = 1;

    // Calculate ceil(lg(n + 1)).
    //
    // We avoid actually calculating n + 1, since
    // that could overflow if n is the largest
    // representable int.
    while ( two_to_k <= n/2 ) {
        ++k;
        two_to_k *= 2;
    }

    ++k;

    std::cout << "ceil(lg(" << n
              << " + 1)) = " << k
              << std::endl;

    return 0;
}
*/























// What did you discover?
//
// For every positive integer n,
//
//     floor(lg(n)) + 1
//
// and
//
//     ceil(lg(n + 1))
//
// have the same value.
//
// In fact, both expressions give the number of
// binary digits required to represent n.
//
// For example,
//
//       n       binary       value
//     -----------------------------
//       1          1           1
//       2         10           2
//       3         11           2
//       4        100           3
//       7        111           3
//       8       1000           4
//      15       1111           4
//      16      10000           5