#include <bitset>
#include <cstdint>
#include <iostream>
#include <limits>

/***************************************************
 * Finding the longest run of bits
 *
 * Write three functions that return:
 *
 *   1. The length of the longest run of consecutive
 *      1 bits.
 *
 *   2. The length of the longest run of consecutive
 *      0 bits.
 *
 *   3. The length of the longest run of identical
 *      bits, whether 0 or 1.
 *
 * For example, consider the 8-bit pattern
 *
 *     00111011
 *
 * Reading from left to right, the runs are
 *
 *     00  111  0  11
 *
 * with lengths
 *
 *      2    3   1   2.
 *
 * Thus,
 *
 *     longest run of 1s = 3
 *     longest run of 0s = 2
 *     longest run        = 3.
 *
 *
 * EXAMINING ONE BIT AT A TIME
 *
 * We can examine each bit using a mask containing
 * exactly one 1:
 *
 *     00000000000000000000000000000001
 *
 * We repeatedly shift this mask to the left:
 *
 *     00000000000000000000000000000001
 *     00000000000000000000000000000010
 *     00000000000000000000000000000100
 *     00000000000000000000000000001000
 *                         ...
 *
 * For each mask, the expression
 *
 *     (n & mask) != 0
 *
 * tells us whether the corresponding bit of n is 1.
 *
 *
 * COUNTING CONSECUTIVE 1 BITS
 *
 * To find the longest run of 1s, we maintain two
 * variables:
 *
 *     count
 *
 * records the length of the run of 1s that we are
 * currently examining, while
 *
 *     result
 *
 * records the longest run seen so far.
 *
 * Whenever the current bit is 1, we increment count.
 * If count is now greater than result, we update
 * result.
 *
 * Whenever the current bit is 0, the current run of
 * 1s has ended, so we reset
 *
 *     count = 0.
 *
 * For example, consider
 *
 *     00111011.
 *
 * Starting at the right and examining one bit at a
 * time, the values of count are
 *
 *     bit:      1  1  0  1  1  1  0  0
 *     count:    1  2  0  1  2  3  0  0
 *
 * The largest value reached by count is 3.
 *
 *
 * COUNTING CONSECUTIVE 0 BITS
 *
 * We could write a second function using essentially
 * the same algorithm to count runs of 0s.
 *
 * There is an easier approach.
 *
 * The bitwise complement
 *
 *     ~n
 *
 * changes every 0 to 1 and every 1 to 0.
 *
 * For example,
 *
 *      n = 00111011
 *     ~n = 11000100
 *
 * Therefore, a run of 0s in n becomes a run of 1s
 * in ~n.
 *
 * Consequently,
 *
 *     longest_run_of_zeros( n )
 *
 * can simply calculate
 *
 *     longest_run_of_ones( ~n ).
 *
 *
 * THE LONGEST RUN OF EITHER BIT
 *
 * The longest run of identical bits must be either
 *
 *   - the longest run of 1s, or
 *   - the longest run of 0s.
 *
 * We can therefore calculate both and return the
 * larger value.
 *
 *
 * FIXED-WIDTH INTEGERS
 *
 * This program uses std::uint32_t so that every
 * value contains exactly 32 bits.
 *
 * This matters when counting runs of 0s. For example,
 *
 *     0
 *
 * has the 32-bit representation
 *
 *     00000000000000000000000000000000
 *
 * and therefore has a run of 32 zeros.
 *
 * Similarly,
 *
 *     11111111111111111111111111111111
 *
 * has a run of 32 ones.
 ***************************************************/

// Function declarations
int main();
unsigned int longest_run_of_ones( std::uint32_t n );
unsigned int longest_run_of_zeros( std::uint32_t n );
unsigned int longest_run( std::uint32_t n );
unsigned int my_max( unsigned int m, unsigned int n );

// Function definitions
int main() {
    for ( std::uint32_t k{ 10 };
          k < 1100;
          k += 13 ) {
        std::cout << std::bitset<32>( k )
                  << "  " << k
                  << std::endl;

        std::cout << "    longest run of 1s: "
                  << longest_run_of_ones( k )
                  << std::endl;

        std::cout << "    longest run of 0s: "
                  << longest_run_of_zeros( k )
                  << std::endl;

        std::cout << "    longest run:       "
                  << longest_run( k )
                  << std::endl << std::endl;
    }

    std::uint32_t all_zeros{ 0 };

    std::cout << std::bitset<32>( all_zeros )
              << "  " << all_zeros
              << std::endl;

    std::cout << "    longest run of 1s: "
              << longest_run_of_ones( all_zeros )
              << std::endl;

    std::cout << "    longest run of 0s: "
              << longest_run_of_zeros( all_zeros )
              << std::endl;

    std::cout << "    longest run:       "
              << longest_run( all_zeros )
              << std::endl << std::endl;


    std::uint32_t all_ones{
        std::numeric_limits<std::uint32_t>::max()
    };

    std::cout << std::bitset<32>( all_ones )
              << "  " << all_ones
              << std::endl;

    std::cout << "    longest run of 1s: "
              << longest_run_of_ones( all_ones )
              << std::endl;

    std::cout << "    longest run of 0s: "
              << longest_run_of_zeros( all_ones )
              << std::endl;

    std::cout << "    longest run:       "
              << longest_run( all_ones )
              << std::endl;

    return 0;
}

/***************************************************
 * longest_run_of_ones
 *
 * Returns the length of the longest sequence of
 * consecutive 1 bits in n.
 ***************************************************/
unsigned int longest_run_of_ones( std::uint32_t n ) {
    unsigned int result{ 0 };
    unsigned int count{ 0 };

    for ( std::uint32_t mask{ 1 };
          mask != 0;
          mask <<= 1 ) {
        if ( (n & mask) != 0 ) {
            ++count;
            result = my_max( result, count );
        } else {
            count = 0;
        }
    }

    return result;
}

/***************************************************
 * longest_run_of_zeros
 *
 * Complementing n changes every 0 bit to a 1 bit.
 * Thus, the longest run of zeros in n is the longest
 * run of ones in ~n.
 ***************************************************/
unsigned int longest_run_of_zeros( std::uint32_t n ) {
    return longest_run_of_ones( ~n );
}

/***************************************************
 * longest_run
 *
 * Returns the length of the longest sequence of
 * identical bits in n.
 ***************************************************/
unsigned int longest_run( std::uint32_t n ) {
    return my_max(
        longest_run_of_ones( n ),
        longest_run_of_zeros( n )
    );
}

/***************************************************
 * my_max
 *
 * Returns the larger of m and n.
 ***************************************************/
unsigned int my_max( unsigned int m, unsigned int n ) {
    if ( m >= n ) {
        return m;
    } else {
        return n;
    }
}