Skip to content

Solución: bits a uno

by en 09/03/2014

¡Hola!

Es el momento de resolver nuestro acertijo de la semana. En él, os preguntábamos el número de bits a 1 que habrá al escribir todos los números dentro de un rango dado.

jserra nos puso su solución en C++. Curiosamente, al ejecutarla con el primer rango que os pedíamos (0 a 8) generaba una violación de segmento por culpa del número 0 🙂 Salvo por eso, el código da la respuesta correcta, ¡enhorabuena!

Sin embargo, tal y como apuntaba después Gualterio, esa solución es muy lenta, pues recorre todos los números en el rango y cuenta sus bits, uno por uno. Eso hace que para averiguar el número de bits a 1 en el rango propuesto por Gualterio, (0 … 2.000.000) necesita más de un segundo. Además… ¡no es en la que estábamos pensando al proponer el acertijo! Aunque sea correcta, no es muy divertida para resolverla a mano y siempre intentamos que nuestros acertijos puedan ser resueltos también por no programadores 😉

Gualterio dio también la respuesta correcta de modo que ¡enhorabuena también! Pero, como de costumbre, prefirió no contar su forma de conseguirla. ¡Sólo el sabrá si utilizó la nuestra! Vamos con ella 🙂

El primer rango era fácil. De hecho, para estar seguros de que se entiende el enunciado la resolveremos escribiendo todos los números, como hacía la solución de jserra.

Número Número en binario Bits a 1
0 0000 0
1 0001 1
2 0010 1
3 0011 2
4 0100 1
5 0101 2
6 0110 2
7 0111 3
8 1000 1
Total 13

El código de jserra y la solución de Gualterio también dijeron 13, y acertaron.

La siguiente pregunta que os hacíamos era el número de bits a 1 necesarios para escribir todos los números entre 9 y 26. La forma manual de responderla es haciéndonos una tabla como la anterior. ¡Pero eso es un rollo! Es mejor pensar un poco 🙂

En primer lugar, el número de bits a 1 en todos los números entre 9 y 26 resulta ser mismo que el número de bits a 1 entre 0 y 26, menos el número de bits en los números entre 0 y 8, que ya conocemos. Es decir, con encontrar una forma rápida de averiguar la cantidad de bits a 1 en todos los números de un rango que empiece en 0 podemos, con una simple resta, obtener la respuesta para un rango que no empiece en 0, como el que nos ocupa ahora. Naturalmente, si siguiéramos usando la solución manual de hacer la tabla esta idea sería contraproducente. Pero resulta mucho más fácil encontrar un modo rápido de contar los bits a 1 de un intervalo si éste empieza por 0 🙂 de modo que esta observación es importante.

Lo que necesitamos, naturalmente, es encontrar esa forma rápida. Para eso, vamos a analizar el rango de los números entre 0 y 26. El número 26 en binario se escribe (1 1010)2 (ponemos el 2 como subíndice para indicar que es un número en base 2). El rango de todos esos números lo podemos separar en dos:

0 0000
0 0001
0 ....
0 1111

1 0000
1 0001
1 ....
1 1010

El primer bloque tiene el bit más significativo (el de la izquierda) a 0, y luego tiene todas las configuraciones de 4 bits. Por tanto, en el primer bloque hay tantos 1’s como sean necesarios para escribir todos los números de 4 bits. Tendremos que buscar una forma de averiguar cuántos son.

Pero antes, vamos con el segundo bloque. En él hay (1 1010)2 − (1 0000)2 +1  números. Quizá te preguntes por qué sumamos uno a la resta. Se debe a que el número con todo a ceros también cuenta. Si dudas, responde a una pregunta ¿cuántos números hay en el rango 0-3, ambos incluidos? Si cuentas, verás que son 4 (0, 1, 2 y 3), o sea (3-0) + 1.

Pero sigamos. Decíamos que hay (1 1010)2 − (1 0000)2 +1  números en el segundo bloque, es decir 11. Todos ellos tienen el bit más significativo a 1, por tanto por culpa de ese bit de la izquierda, el rango 0 … 26 tiene 11 bits a 1 más. Además, tenemos que sumar todos los bits a 1 debidos a la escritura de los otros cuatro bits, es decir, los bits a 1 que se necesitan para escribir el rango de (0000)2 a (1010)2 o, dicho de otro modo, el número de bits a 1 en el rango 0..10 (en decimal).

Recapitulando, poniéndolo todo en decimal:

BitsAUno(0..26) = BitsAUno(4 bits) + 11 + BitsAUno(0..10)

¡Parece que hemos vuelto al principio! Para calcular el número de bits a 1 del rango 0 … 26 necesitamos saber el número de bits a 1 del rango 0 … 10. Pero esto ¡es un avance, porque el rango es más pequeño! Y no sólo es más pequeño; también tiene un bit menos. Podemos repetir el proceso que hemos seguido con el nuevo rango 0 … 10, que podemos dividir así:

0 000
0 001
....
0 111

1 000
1 ...
1 010

¿Veis la idea? Ahora todo es un poco más pequeño. En el primer bloque tenemos tantos 1’s como se necesiten para escribir todos los números de 3 bits. En el segundo bloque tenemos varios números (3) con el bit más significativo a 1, y luego los 1’s necesarios para escribir el rango (000)2-(010)2. Por tanto:

BitsAUno(0..26) = BitsAUno(4 bits) + 11 + BitsAUno(3 bits) + 3 + BitsAUno(0..2)

Una vez cogida la idea, calcular BitsAUno(0..2) con el mismo procedimiento resulta sencillo, y la suma final queda:

BitsAUno(0..26) = BitsAUno(4 bits) + 11 +
BitsAUno(3 bits) + 3 +
BitsAUno(1 bit) + 1

Ya sólo nos falta saber calcular cuántos 1’s son necesarios para escribir todos los números con una cantidad específica de bits. Pero eso lo podemos hacer utilizando la misma idea. Por comodidad, construyámosla al contrario. Para escribir los números con 0 bits no necesitamos ningún 1. Para los números con un bit, necesitamos solamente un 1. Para dos bits, necesitamos dos veces los necesarios con un bit, más dos por los dos bits de la izquierda de 102 y 112. En total, 4.

Para tres bits necesitamos dos veces los necesarios para 2 bits, más cuatro, por el bit más significativo de los números 1002 … 1112. Si lo pensáis un poco, llegaréis a la fórmula:

BitsAUno(i bits) = 2×BitsAUno(i-1 bits) + 2i-1

cuyos valores para los primeros números son:

Ancho Bits a 1 0..2ancho-1
0 0
1 1
2 4
3 12
4 32
5 80
6 192
7 448
8 1024

¡Con esto ya casi está! Si, con los valores de esta tabla, completáis las cuentas pendientes, veréis que los bits a 1 necesarios para los números entre 0 y 26 son 60. Si les quitamos los 13 del rango 0 … 8 que calculamos antes, nos quedan 47, tal y como dijo Gualterio y como contestaba el programa de jserra.

Es posible que penséis que esto es demasiado lío para llegar a esa respuesta, y que es más rápido ponerse todos los números. Pero ¡no es así! Para demostrarlo, resolvamos la última pregunta, el rango 99 y 321. Primero sacamos el número de bits a 1 para escribir todos los números entre 0 y 98. Basta escribir el número en binario:

98 = (1100010)2

Y ahora ir diseccionándolo quitándole los bits de izquierda a derecha para llegar a la suma:

BitsAUno(0..98) = 192 + 35 + 80 + 3 + 1 + 1 = 312

De la misma forma, para 321 (101000001 en binario)

BitsAUno(0..321) = 1024 + 66 + 192 + 2 + 1 = 1285

Si los restamos llegamos al 973 que nos dijo Gualterio.

Mucho más rápido, ¿verdad? Con esta idea, ahora ya sí estáis preparados para afrontar rangos aún más grandes. ¿Alguien se atreve a usar este método con el reto de Gualterio, de todos los números entre 0 y 2.000.000.000? Si lo resolvéis y lo programáis, podéis, como siempre, probar vuestra solución aquí.

¡Hasta el próximo!

Anuncios

From → Soluciones

One Comment
  1. Gualterio permalink

    Hooola,

    Pues sí, confirmo que lo había hecho así 😉

    Ya estoy esperando el siguiente acertijo… 🙂

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: