Verifique si un número es divisible por 3

Escribir código para determinar si un número es divisible por 3. La entrada a la función es un bit único , 0 o 1, y la salida debe ser 1 si el número recibido hasta ahora es la representación binaria de un número divisible por 3, de lo contrario cero.

Ejemplos:

input "0": (0) output 1 inputs "1,0,0": (4) output 0 inputs "1,1,0,0": (6) output 1 

Esto se basa en una pregunta de entrevista. Solicito un dibujo de compuertas lógicas, pero dado que esto es stackoverflow, aceptaré cualquier lenguaje de encoding. Puntos de bonificación para una implementación de hardware (verilog, etc.).

Parte a (fácil): la primera entrada es el MSB.

Parte b (un poco más difícil): la primera entrada es el LSB.

Parte c (difícil): ¿Cuál es más rápido y más pequeño, (a) o (b)? (No teóricamente en el sentido Big-O, pero prácticamente más rápido / más pequeño.) Ahora toma el más lento / más grande y hazlo tan rápido / pequeño como el más rápido / más pequeño.

    Heh

    Tabla de estado para LSB:

     SIS' O 0 0 0 1 0 1 1 0 1 0 2 0 1 1 0 1 2 0 1 0 2 1 2 0 

    Explicación: 0 es divisible por tres. 0 << 1 + 0 = 0 . Repita usando S = (S << 1 + I) % 3 y O = 1 si S == 0 .

    Tabla de estados para MSB:

     SIS' O 0 0 0 1 0 1 2 0 1 0 1 0 1 1 0 1 2 0 2 0 2 1 1 0 

    Explicación: 0 es divisible por tres. 0 >> 1 + 0 = 0 . Repita usando S = (S >> 1 + I) % 3 y O = 1 si S == 0 .

    S' es diferente de arriba, pero O funciona igual, ya que S' es 0 para los mismos casos (00 y 11). Como O es el mismo en ambos casos, O_LSB = O_MSB, por lo tanto, para hacer MSB tan corto como LSB, o viceversa, solo use el más corto de ambos.

    Existe un truco bastante conocido para determinar si un número es un múltiplo de 11, al sumr y restar alternativamente sus dígitos decimales. Si el número que obtiene al final es un múltiplo de 11, entonces el número con el que comenzó también es un múltiplo de 11:

     47278 4 - 7 + 2 - 7 + 8 = 0, múltiplo de 11 (47278 = 11 * 4298)
     52214 5 - 2 + 2 - 1 + 4 = 8, no múltiplo de 11 (52214 = 11 * 4746 + 8)
    

    Podemos aplicar el mismo truco a los números binarios. Un número binario es un múltiplo de 3 si y solo si la sum alternante de sus bits es también un múltiplo de 3:

     4 = 100 1 - 0 + 0 = 1, no múltiplo de 3
     6 = 110 1 - 1 + 0 = 0, múltiplo de 3
     78 = 1001110 1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, múltiplo de 3
     109 = 1101101 1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, no múltiplo de 3
    

    No importa si comienza con el MSB o el LSB, entonces la siguiente función de Python funciona igual de bien en ambos casos. Se necesita un iterador que devuelve los bits uno a la vez. multiplier alterna entre 1 y 2 en lugar de 1 y -1 para evitar tomar el módulo de un número negativo.

     def divisibleBy3(iterator): multiplier = 1 accumulator = 0 for bit in iterator: accumulator = (accumulator + bit * multiplier) % 3 multiplier = 3 - multiplier return accumulator == 0 

    Aquí … algo nuevo … cómo verificar si un número binario de cualquier longitud (incluso miles de dígitos) es divisible entre 3.

    texto alternativo http://sofes.miximages.com/puzzle/23oe41.png

     -->((0))<---1--->()<---0--->(1) ASCII representation of graph 

    De la imagen.

    1) Comienzas en el doble círculo. 2) Cuando obtienes uno o un cero, si el dígito está dentro del círculo, entonces te mantienes en ese círculo. Sin embargo, si el dígito está en una línea, entonces cruzas la línea. 3) Repita el paso dos hasta que se completen todos los dígitos. 4) Si finalmente terminas en el círculo doble, entonces el número binario es divisible por 3.

    También puede usar esto para generar números divisibles por 3. Y no me gustaría obtener imágenes, sería difícil convertir esto en un circuito.

    1 ejemplo usando el gráfico …

    11000000000001011111111111101 es divisible por 3 (termina en el doble círculo nuevamente)

    Pruébalo por ti mismo.

    También puede hacer trucos similares para realizar MOD 10, para convertir números binarios en números base 10. (10 círculos, cada uno doblado en un círculo y representan los valores 0 a 9 resultantes del módulo)

    EDITAR: Esto es para dígitos que se ejecutan de izquierda a derecha, aunque no es difícil modificar la máquina de estados finitos para que acepte el lenguaje inverso.

    NOTA: En la representación ASCII del gráfico () denota un círculo único y (()) denota un círculo doble. En las máquinas de estados finitos estos se llaman estados, y el doble círculo es el estado de aceptación (el estado que significa que es divisible por 3)

    Aquí hay una manera simple de hacerlo a mano. Como 1 = 2 2 mod 3, obtenemos 1 = 2 2n mod 3 por cada entero positivo. Además 2 = 2 2n + 1 mod 3. Por lo tanto, se puede determinar si un entero es divisible por 3 contando los 1 bit en las posiciones de bit impares, multiplicar este número por 2, agregar el número de 1 bit a bit posistions agregarlos al resultado y verifica si el resultado es divisible por 3.

    Ejemplo: 57 10 = 111001 2 . Hay 2 bits en posiciones impares y 2 bits en posiciones pares. 2 * 2 + 2 = 6 es divisible por 3. Por lo tanto, 57 es divisible por 3.

    Aquí también hay un pensamiento para resolver la pregunta c). Si uno invierte el orden de bits de un entero binario, todos los bits permanecen en posiciones pares / impares o todos los bits cambian. Por lo tanto, invertir el orden de los bits de un entero n results es un entero que es divisible por 3 si y solo si n es divisible por 3. Por lo tanto, cualquier solución para la pregunta a) funciona sin cambios para la pregunta b) y viceversa. Hmm, tal vez esto podría ayudar a averiguar qué enfoque es más rápido …

    Debe hacer todos los cálculos usando el módulo aritmético 3. Este es el camino

    MSB:

     number=0 while(!eof) n=input() number=(number *2 + n) mod 3 if(number == 0) print divisible 

    LSB:

     number = 0; multiplier = 1; while(!eof) n=input() number = (number + multiplier * n) mod 3 multiplier = (multiplier * 2) mod 3 if(number == 0) print divisible 

    Esta es una idea general …

    Ahora, tu parte es entender por qué esto es correcto.

    Y sí, haz la tarea tú mismo;)

    La idea es que el número puede crecer arbitrariamente, lo que significa que no puedes usar mod 3 aquí, ya que tu número crecerá más allá de la capacidad de tu clase entera.

    La idea es notar lo que sucede con el número. Si agrega bits a la derecha, lo que está haciendo en realidad es desplazar un bit a la izquierda y agregar el nuevo.

    Shift-left es lo mismo que multiplicar por 2, y agregar el nuevo bit agrega 0 o 1. Suponiendo que comenzamos desde 0, podemos hacer esto recursivamente en base al módulo-3 del último número.

     last | input || next | example ------------------------------------ 0 | 0 || 0 | 0 * 2 + 0 = 0 0 | 1 || 1 | 0 * 2 + 1 = 1 1 | 0 || 2 | 1 * 2 + 0 = 2 1 | 1 || 0 | 1 * 2 + 1 = 0 (= 3 mod 3) 2 | 0 || 1 | 2 * 2 + 0 = 1 (= 4 mod 3) 2 | 1 || 2 | 2 * 2 + 1 = 2 (= 5 mod 3) 

    Ahora veamos qué sucede cuando agrega un poco a la izquierda. Primero, note que:

    2 2n mod 3 = 1

    y

    2 2n + 1 mod 3 = 2

    Entonces ahora tenemos que agregar 1 o 2 al mod basado en si la iteración actual es impar o par.

     last | n is even? | input || next | example ------------------------------------------- d/c | don't care | 0 || last | last + 0*2^n = last 0 | yes | 1 || 0 | 0 + 1*2^n = 1 (= 2^n mod 3) 0 | no | 1 || 0 | 0 + 1*2^n = 2 (= 2^n mod 3) 1 | yes | 1 || 0 | 1 + 1*2^n = 2 1 | no | 1 || 0 | 1 + 1*2^n = 0 (= 3 mod 3) 1 | yes | 1 || 0 | 2 + 1*2^n = 0 1 | no | 1 || 0 | 2 + 1*2^n = 1 

    En realidad, el método LSB realmente lo haría más fácil. Cª:

    Método MSB:

     /* Returns 1 if divisble by 3, otherwise 0 Note: It is assumed 'input' format is valid */ int is_divisible_by_3_msb(char *input) { unsigned value = 0; char *p = input; if (*p == '1') { value &= 1; } p++; while (*p) { if (*p != ',') { value <<= 1; if (*p == '1') { ret &= 1; } } p++; } return (value % 3 == 0) ? 1 : 0; } 

    Método LSB:

     /* Returns 1 if divisble by 3, otherwise 0 Note: It is assumed 'input' format is valid */ int is_divisible_by_3_lsb(char *input) { unsigned value = 0; unsigned mask = 1; char *p = input; while (*p) { if (*p != ',') { if (*p == '1') { value &= mask; } mask <<= 1; } p++; } return (value % 3 == 0) ? 1 : 0; } 

    Personalmente, me cuesta creer que uno de estos sea significativamente diferente al otro.

     input "0": (0) output 1 inputs "1,0,0": (4) output 0 inputs "1,1,0,0": (6) output 1 

    ¿No debería esta última entrada ser 12 , o estoy malentendiendo la pregunta?

    Creo que Nathan Fellman está en el camino correcto para la parte ayb (excepto que b necesita una porción adicional de estado: necesita mantener un registro de si la posición de su dígito es impar o par).

    Creo que el truco para la parte C es negar el last valor en cada paso. Es decir 0 va a 0, 1 va a 2 y 2 va a 1.

    Un número es divisible por 3 si la sum de sus dígitos es divisible por 3.
    Entonces puede agregar los dígitos y obtener la sum:
    – si la sum es mayor o igual a 10, use el mismo método
    – si es 3,6,9, entonces es divisible
    – si la sum es diferente a 3,6,9, entonces no es divisible