C-Addition unter Verwendung des Moduls

81

Ich bin auf einen faszinierenden C-Code gestoßen A + B, der gedruckt wird , aber ich habe Probleme, ihn zu verstehen.

Eingabeformat:

A B

wo A, Bganze Zahlen zwischen 0und 10durch ein Leerzeichen getrennt.

Code:

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

Dies war für die Kurzcodierung gedacht, bitte beachten Sie die Warnungen.

Was ich bisher verstehe:

gets( &n )speichert die ASCII-Werte von A, Leerzeichen und B in den unteren drei Bytes von n. Zum Beispiel A = 3und B = 8würde nachgeben n = 0x00382033. Gegebene Bedingungen verhindern ein nÜberlaufen. Aber ich verstehe nicht, wie n % 85 - 43Erträge A + B.

Wie kommst du auf diese Zahlen?

c addition mod William Lee
quelle
2
In der Tat faszinierend.
Havenard
12
Ein Hinweis ist, dass 85 Bits in Binärform abwechseln 01010101. Wenn Sie diesen Ansatz mit 10101010der Nummer 170 versuchen , erhalten Sie eine ähnliche Funktionalität. Der einzige Unterschied besteht darin, dass Sie 0 0stattdessen die Nummer 128 erhalten (die 10000000binär ist). Eine ähnliche Technik wird verwendet, um eine Reihe von Optimierungen mit bitweisen Operationen durchzuführen, wie z. B. das Zählen der Anzahl von Bits in einem gesetzten Bit unter Verwendung von Masken wie 0x55555555und 0xAAAAAAAA(0x55 = 85 und 0xAA = 170). Wenn Sie diese hexadezimalen Codes googeln, erhalten Sie eine Reihe interessanter Artikel.
Havenard
Wow, ich hätte nie so viel Tiefe in der Nummer 85 erwartet. Danke für den Einblick.
William Lee
1
Ich nehme an, Sie meinen zwischen 0 und 9 einschließlich?
Pipe
1
Das ist definitiv ioccc würdig.
dgnuff

Antworten:

87

Mit Little-Endian-Ints (und unter der Annahme von ASCII-Text und 8-Bit-Bytes und allen anderen Annahmen, die der Code erfordert) und dem Ignorieren aller technisch falschen modernen C-Inhalte im Code ist Ihr "Was ich verstehe soweit "ist richtig.

gets(&n)speichert die ASCII-Werte von A, Leerzeichen und B in den ersten 3 Bytes von n. Es wird auch ein Null-Terminator im 4. Byte gespeichert. Speichern von ASCII jene Werte in diese Bytes nErgebnisse in nden Wert nehmen B*256*256 + space*256 + A, wo B, spaceund Astellen die entsprechenden ASCII - Werten.

256 mod 85 ist 1, also durch die Eigenschaften der modularen Arithmetik,

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

Übrigens bekommen wir mit 4-Byte-Big-Endian-Ints

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

Endianness spielt also keine Rolle, solange wir 4-Byte-Ints haben. (Größere oder kleinere Ints könnten ein Problem sein. Bei 8-Byte-Ints müssten wir uns beispielsweise Gedanken darüber machen, was in den Bytes enthalten ist n, getsdie nicht festgelegt wurden.)

Das Leerzeichen ist ASCII 32 und der ASCII-Wert für ein Ziffernzeichen ist 48 + der Wert der Ziffer. Definieren aund bals numerische Werte der eingegebenen Ziffern (anstelle der ASCII-Werte der Ziffernzeichen) haben wir

(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

wobei die letzten beiden Äquivalenzen auf der Tatsache beruhen, dass aund bWerte von 0 bis 9 annehmen.

user2357112 unterstützt Monica
quelle