#include <cstdint>
#include <iostream>

/***************************************************
 * Guessing a 64-bit unsigned integer
 *
 * A 64-bit unsigned integer can have any value from
 *
 *     0
 *
 * through
 *
 *     18446744073709551615.
 *
 * There are therefore
 *
 *     18446744073709551616
 *
 * different 64-bit unsigned integers. This is
 *
 *     2^64
 *
 * possible values.
 *
 * Suppose you were asked to play a high-low guessing
 * game in which another person chooses one of these
 * integers and you must determine the number.
 *
 * Where should you start?
 *
 *
 * A SMALLER EXAMPLE
 *
 * If you were asked to guess an integer between 0
 * and 100, you might begin near the middle:
 *
 *     50.
 *
 * If that guess were too large, you would next
 * search the lower half. If it were too small, you
 * would search the upper half.
 *
 * Each comparison allows you to eliminate
 * approximately half of the remaining possibilities.
 *
 *
 * A 64-BIT INTEGER
 *
 * How can we apply the same idea when there are
 *
 *     2^64
 *
 * possible values?
 *
 * The binary representation gives us a particularly
 * convenient solution.
 *
 * A 64-bit unsigned integer has the form
 *
 *     b63 b62 b61 ... b2 b1 b0
 *
 * where each bit is either 0 or 1.
 *
 * We can determine the number one bit at a time,
 * beginning with the most significant bit.
 *
 *
 * THE FIRST GUESS
 *
 * Begin with the mask
 *
 *     10000000000000000000000000000000
 *     00000000000000000000000000000000
 *
 * where the single 1 is bit 63.
 *
 * In hexadecimal, this is much easier to write:
 *
 *     0x8000000000000000.
 *
 * If this value is no greater than the target, then
 * bit 63 of the target must be 1, so we keep that
 * bit in our guess.
 *
 * Otherwise, bit 63 must be 0.
 *
 *
 * THE NEXT BIT
 *
 * We then shift the mask one position to the right:
 *
 *     mask >>= 1;
 *
 * The mask is now
 *
 *     01000000000000000000000000000000
 *     00000000000000000000000000000000.
 *
 * We temporarily set this bit in our current guess:
 *
 *     guess | mask
 *
 * If
 *
 *     (guess | mask) <= target,
 *
 * then we know that this bit can also be set to 1:
 *
 *     guess |= mask;
 *
 * Otherwise, we leave the bit as 0.
 *
 * We continue from the most significant bit down to
 * the least significant bit.
 *
 *
 * WHY DOES THIS WORK?
 *
 * At every step, guess is the largest value we have
 * constructed so far that does not exceed target.
 *
 * When we consider the next bit, there are only two
 * possibilities:
 *
 *     leave the bit as 0
 *
 * or
 *
 *     set the bit to 1.
 *
 * Testing
 *
 *     guess | mask
 *
 * tells us whether setting that bit would make our
 * guess larger than the target.
 *
 * Thus, each comparison determines one bit of the
 * target.
 *
 *
 * HOW MANY COMPARISONS?
 *
 * There are 64 bits to determine. Consequently, we
 * need at most 64 comparisons of a candidate guess
 * with the target.
 *
 * Contrast this with the original loop:
 *
 *     while ( guess != target ) {
 *         ++guess;
 *     }
 *
 * For the target used below, that loop would require
 * more than 18 quintillion increments.
 *
 * The bitwise algorithm requires at most 64 steps.
 ***************************************************/

// Function declaration
int main();

// Function definition
int main() {
    // The number to guess:
    std::uint64_t target{
        UINT64_C( 18337158320539853209 )
    };

    std::cout << "The target: "
              << target
              << std::endl;

    std::uint64_t guess{ 0 };

    while ( guess != target ) {
        ++guess;
    }

    std::cout << "Found it:   "
              << guess
              << std::endl;

    return 0;
}




















// Hint:
//
// Start by considering the most significant bit.
//
// A number approximately halfway between 0 and
// 2^64 - 1 is
//
//     0x8000000000000000
//
// which in binary is
//
//     0b10000000000000000000000000000000
//       00000000000000000000000000000000
//
// There is one 1 followed by 63 zeros.
//
// What should the next candidate be if this value
// is too large?
//
// What should the next candidate be if this value
// is too small?
//
// The next bit to consider is bit 62:
//
//     0b11000000000000000000000000000000
//       00000000000000000000000000000000
//
// or
//
//     0b01000000000000000000000000000000
//       00000000000000000000000000000000.
//
// Continue determining the bits from left to right.











































// Here is one solution.
//
// Question:
//
// What is the maximum number of comparisons between
// a candidate guess and the target?

/*
int main() {
    // The number to guess:
    std::uint64_t target{
        UINT64_C( 18337158320539853209 )
    };

    std::cout << "The target: "
              << target
              << std::endl;

    std::uint64_t mask{
        std::uint64_t{ 1 } << 63
    };

    std::uint64_t guess{ 0 };

    while ( mask != 0 ) {
        // Temporarily set the bit identified by mask.
        // If this does not make the guess larger than
        // the target, keep the bit set.

        if ( (guess | mask) <= target ) {
            guess |= mask;

            if ( guess == target ) {
                break;
            }
        }

        // Move to the next bit to the right.
        mask >>= 1;
    }

    std::cout << "Found it:   "
              << guess
              << std::endl;

    return 0;
}
*/