comprobar si un número binario sin signo es divisible por 15

Question

Soy una estudiante de informática y me he quedado prendado de esta cuestión de horas.

Tenemos un binario sin signo número X, representada por 12 bits. Nos gustaría construir un sistema con 1 bit de salida - Y, que será '1' si X es dividido por 15 sin un resto.

Los únicos componentes que podemos utilizar son:

• 4 bits sumador, habiendo también C0 (llevar) como entrada, y C4 como de salida.
• 1 sola puerta NOR con 3 entradas.

Me hizo encontrar un patrón. Si voy a calcular 2^i % 15 0<=i<=11 (ya que es de 12 bits), entonces para que voy a obtener una secuencia de 1248 1248 1248.

Y si tengo 0001 1110 1111, a continuación, sólo puedo múltiples de todos los dígitos, la suma de ellos, y comprobar si mi número es divisible por 15.

0 + 0 + 0 + 8 + 1 + 2 + 4 + 0 + 1 + 2 + 4 + 8 = 30

El problema es que no tengo ni idea de cómo implementarlo, y si es eficiente.

Me gustaría un poco de ayuda.

Answer 1

¿Sabe usted cómo comprobar la divisibilidad por 9 en base 10?

Agregar todos los dígitos, usando de base 10 de la aritmética. Si el resultado tiene varios dígitos, repita el proceso. Se detiene cuando usted tiene un dígito. Si el dígito es 9, el número original era divisible por 9. Esto funciona porque el divisor está siendo probada base-1. Por ejemplo 45 es divisible por 9, y los dígitos de la suma de 9, solo una serpiente que se necesita de dos dígitos. 999 es demasiado, los dos sumandos son necesarios para los tres dígitos.

Así que ahora tienes una sugerencia de cómo comprobar la divisibilidad por 15 cuando usted tiene la base 16 de la aritmética de las instalaciones a la mano?

Answer 2

La técnica es similar a lo que usted haría para comprobar si un número es divisible por 9 en decimal. Necesitamos dividir el número de cuatro bits dígitos y, a continuación, añadir los dígitos juntos varias veces hasta que tenemos un solo dígito a la izquierda.

Permite llamar a los dígitos X Y Z

c1,r1 = X + Y
c2,r2 = Z + r1 + c1
c3,r3 = r2 + 1

SI X,Y,Z es divisible por 15 entonces c2,r2 también es divisible por 15. Además c2,r2 es menor que 0x1e. Así que si r=15, entonces el número original era divisible por 15. Prueba si r es igual a 15 mediante la adición de uno y mirando el resultado de llevar la bandera.

Lo que es desconcertante mí es lo que la puerta nor se supone debe ser para.

Answer 3

La respuesta completa:

Como @Neil_UK dijo, tengo 12 bits, y si quiero comprobar si el número es divisible por 15, yo tomo a los 12 bits, y mira como 3 números en base 16.

Puedo añadir los tres números juntos, mientras que añadir siempre la llevan a la siguiente adder.

Después de agregar todos ellos, voy a obtener como resultado un número. Como ya he dicho, queremos ver si el número es divisible por 15, y porque los números están en la base 16, por lo que si el resultado es 15 - el número es divisible por 15.

Si ese número es 15 en binario, 1111, así que si voy a agregar 1 a 1111, voy a conseguir llevar a 1 y 0000.

Si ese número es 0 en binario, 0000, así que si voy a agregar 1 a 0000, voy a tener 0001.

Aquí es donde el NI viene a jugar.

El número es divisible por 15 si los 3 últimos dígitos son 0.

El circuito:

Por ejemplo:

1111 1111 1111:

• 1111+1111 + 1 = llevar a 1 y 1111
• 1111 + 1111 + llevar a 1 = llevar a 1 y 1111
• 1111 + llevar a 1 = llevar a 1 y 0000
• NI el(0,0,0)=True

0001 1001 0101: (405):

• 0101+ 1001+1= 1111
• 1111 + 0001 = llevar a 1 y 0000
• 0000 + llevar a 1 = 0001
• NI el(0,0,0)=True