Authors: Ernestico, frankr, bestard

El problema nos pide encontrar la cantidad de números en el intervalo ~[a,b]~ que contienen exactamente n bits activos en su notación en binario. Sea ~g(a,b,n)~ la solución a nuestro problema, luego \(g(a,b,n) = f(b,n) – f(a-1,n)\) donde ~f(x,n)~ es la cantidad de números en el intervalo ~[1,x]~ que contienen n bits activos en su notación en binario. Entonces el problema que tenemos ahora es calcular ~f(x,n)~, para ello lo primero es llevar a ~x~ a binario. Sea ~d~ la cantidad de dígitos de ~x~ (en binario), luego la cantidad de números de hasta ~d-1~ dígitos que tienen ~n~ bits activos seria ~C(d-1,n)~ que denota la combinatoria de ~d-1~ objetos en ~n~ lugares. Luego resta contar los números menores que ~x~ que tienen ~d~ dígitos. Para ello iteramos por los dígitos de ~x~, desde el bit más significativo al menos significativo, si el bit i esta encendido contamos la cantidad de números que son iguales a ~x~ hasta el bit ~i-1~ ( en este caso el bit ~i-1~ es más significativo que el bit ~i~ ) y que tiene el bit i apagado, que sería ~C(d-i,b)~, donde ~d-i~ es la cantidad de lugares que me restan por analizar y ~b~ es la cantidad de bits que me faltan por colocar, es decir, ~n~ – bits activos en ~x~ hasta el bit ~i-1~. El único caso que resta es contar que el propio ~x~ tenga ~n~ bits activos. Complejidad: ~O(logx)~.