Maria comenzó a trabajar en la biblioteca de la universidad, en la cual llevan el registro de los libros prestados por estante, esto lo almacenan como una cadena binaria de 1 y 0 donde el 1 significa que el espacio está disponible en el estante. Maria ha decidido optimizar cómo se representan los estantes, así que en lugar de representarlos como grandes 1 y 0 ahora los representa como un número en su representación decimal, pero se dio cuenta que esto presenta un problema ya que una consulta que normalmente se usa en la biblioteca es ver la franja más grande de libros prestados en un estante.
María está convencida que su representación aún es viable, y le pide ayuda para realizar la operación de saber cual es la franja de libros prestados más grande en un estante dada la nueva representación.
Entrada
La entrada contiene múltiples líneas que serán leídas hasta final de archivo. Cada línea de entrada consiste en un único valor N Que representa la un estante de libros con la representación propuesta por Maria. 0≤N≤18446744073709551614
Salida
Por cada caso imprima una línea con el valor del mayor espacio disponible.
Según la descripción del problema, se representa el estante de la biblioteca con una cadena conformada por 0 y 1, donde 1 indica que el estante está vacío y 0 que está lleno. El problema que se debe resolver es encontrar la longitud de la subcadena conformada por 1s únicamente, por ejemplo, si la cadena es 1011011110, la respuesta es 4.
Sin embargo, la entrada del problema es un entero en base 10, y se debe trabajar en base 2 para resolver el problema. Para ello, se puede obtener el bit menos significativo con la operación mod 2, para 'iterar' sobre la cadena binaria, se realiza un corrimiento a la derecha, dividiendo n entre 2. Si este proceso se realiza mientras n > 0, se habrá recorrido toda la cadena. Para encontrar la cadena mas larga, se van sumando los 1 hasta que se encuentre un 0, en ese momento, se actualiza la respuesta de la subcadena mas larga.
La complejidad total es O(log2(n)).
NOTA: n puede ser muy grande, en el peor caso puede ser 264−2. El límite de un tipo de dato entero es 232−1, el de un long long es 263−1, por lo cual es necesario utilizar unsigned long long, cuyo valor máximo es 264−1.
Solución en C++: https://gist.github.com/afcruzs/4a0b1e6299ea41ca3c14b32b40b65abf
