Suma de C usando módulo

81

Me encontré con un código C intrigante que se imprime A + B, pero tengo problemas para entenderlo.

Formato de entrada:

A B

donde A, Bson números enteros entre 0y 10separados por un solo espacio.

Código:

main( n )
{
    gets( &n );
    printf("%d", n % 85 - 43);
}

Esto fue diseñado para codificación corta, no te preocupes por las advertencias.

Lo que entiendo hasta ahora:

gets( &n )almacena los valores ASCII de A, espacio y B en los tres bytes inferiores de n. Por ejemplo, A = 3y B = 8cedería n = 0x00382033. Las condiciones dadas evitan que se ndesborde. Pero no entiendo cómo n % 85 - 43cede A + B.

¿Cómo se les ocurren estos números?

c addition mod William Lee
fuente
2
Realmente intrigante.
Havenard
12
Una sugerencia es que 85 es los bits alternantes en binario, 01010101. Si prueba este enfoque con 10101010, que es el número 170, obtiene una funcionalidad similar, la única diferencia es que si lo hace 0 0, obtiene el número 128 (que está 10000000en binario). Se utiliza una técnica similar para hacer un montón de optimizaciones con operaciones bit a bit, como contar el número de bits en un conjunto de bits utilizando máscaras como 0x55555555y 0xAAAAAAAA(0x55 = 85 y 0xAA = 170). Si busca en Google esos códigos hexadecimales, obtendrá un montón de artículos interesantes.
Havenard
Vaya, nunca esperé tanta profundidad en el número 85. Gracias por la información.
William Lee
1
Supongo que te refieres a entre 0 y 9 inclusive.
tubería el
1
Eso es definitivamente digno de ioccc .
dgnuff

Respuestas:

87

Con ints little-endian (y asumiendo texto ASCII y bytes de 8 bits, y todas las demás suposiciones que requiere el código), e ignorando todas las cosas técnicamente incorrectas en C moderno en el código, su "Lo que entiendo hasta ahora "es correcto.

gets(&n)almacenará los valores ASCII de A, espacio y B en los primeros 3 bytes de n. También almacenará un terminador nulo en el cuarto byte. El almacenamiento de esos valores ASCII en esos bytes de nresultados en ntomando el valor B*256*256 + space*256 + A, donde B, spacey Arepresentar los valores ASCII correspondientes.

256 mod 85 es 1, por lo que según las propiedades de la aritmética modular,

(B*256*256 + space*256 + A) % 85 = (B + space + A) % 85

Por cierto, con ints big-endian de 4 bytes, obtenemos

(A*256*256*256 + space*256*256 + B*256) % 85 = (B + space + A) % 85

así que endianness no importa, siempre que tengamos entradas de 4 bytes. (Los ints más grandes o más pequeños podrían ser un problema; por ejemplo, con ints de 8 bytes, tendríamos que preocuparnos por lo que hay en los bytes nque getsno se configuraron).

El espacio es ASCII 32 y el valor ASCII para un carácter de dígito es 48 + el valor del dígito. Definiendo ay bcomo los valores numéricos de los dígitos ingresados ​​(en lugar de los valores ASCII de los caracteres de dígitos), tenemos

(B + space + A) % 85 = (b + 48 + 32 + a + 48) % 85
                     = (a + b + 128) % 85
                     = (a + b + 43) % 85

(B + space + A) % 85 - 43 = (a + b + 43) % 85 - 43
                          = (a + b) % 85
                          = a + b

donde las dos últimas equivalencias se basan en el hecho de que ay btoman valores de 0 a 9.

user2357112 es compatible con Monica
fuente