80

I came across an intriguing C code that prints A + B, but I have trouble understanding it.

Input Format:

A B

where A, B are integers between 0 and 10 separated by a single space.

Code:

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

This was intended for short coding, please don't mind the warnings.

What I understand so far:

gets( &n ) stores the ASCII values of A, space, and B in the lower three bytes of n. For example, A = 3 and B = 8 would yield n = 0x00382033. Given conditions prevent n from overflowing. But I do not understand how n % 85 - 43 yields A + B.

How do you come up with these numbers?

Community
  • 1
  • 1
William Lee
  • 590
  • 4
  • 8
  • 2
    Intriguing indeed. – Havenard Jul 19 '18 at 05:15
  • 12
    A hint is that 85 is alternating bits in binary, `01010101`. If you try this approach with `10101010`, that is the number 170, you get similar functionality, the only difference being if you do with `0 0` you get the number 128 instead (which is `10000000` in binary). A similar technique is used to do a bunch of optimizations with bitwise operations such as counting number of bits in a bit set using masks such as `0x55555555` and `0xAAAAAAAA` (0x55 = 85 and 0xAA = 170). If you google those hexadecimal codes you get a bunch of interesting articles. – Havenard Jul 19 '18 at 05:33
  • Wow, i never expected this much depth in the number 85. Thanks for the insight. – William Lee Jul 19 '18 at 06:35
  • 1
    I assume you mean between 0 and 9 inclusive? – pipe Jul 19 '18 at 16:52
  • 1
    That's definitely [ioccc](https://www.ioccc.org/) worthy. – dgnuff Jul 19 '18 at 20:02

1 Answers1

87

With little-endian ints (and assuming ASCII text, and 8-bit bytes, and all the other assumptions the code requires), and ignoring all the technically-wrong-in-modern-C stuff in the code, your "What I understand so far" is correct.

gets(&n) will store the ASCII values of A, space, and B into the first 3 bytes of n. It'll also store a null terminator into the 4th byte. Storing those ASCII values into those bytes of n results in n taking the value B*256*256 + space*256 + A, where B, space, and A represent the corresponding ASCII values.

256 mod 85 is 1, so by the properties of modular arithmetic,

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

Incidentally, with 4-byte big-endian ints, we get

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

so endianness doesn't matter, as long as we have 4-byte ints. (Bigger or smaller ints could be a problem; for example, with 8-byte ints, we'd have to worry about what's in the bytes of n that gets didn't set.)

Space is ASCII 32, and the ASCII value for a digit character is 48 + the value of the digit. Defining a and b as the numeric values of the digits entered (rather than the ASCII values of the digit characters), we have

(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

where the last two equivalences rely on the fact that a and b take values from 0 to 9.

user2357112
  • 260,549
  • 28
  • 431
  • 505