使用模运算的C语言加法

Question

我发现了一段有趣的C代码，它打印出A + B，但是我理解起来有些困难。

输入格式：

A B

其中A和B是两个整数，它们的取值范围在0到10之间，用一个空格分隔。

代码：

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

这段代码设计用于短码，请忽略警告。

目前的理解：

gets( &n ) 将A，空格和B的ASCII值存储在n的低三个字节中。例如，A = 3 和 B = 8 将产生n = 0x00382033。给定条件防止n溢出。但我不明白为什么n % 85 -43会得到A + B。

你是如何想出这些数字的？

- William Lee

---

确实很有趣。 - Havenard

提示是85的二进制交替位为01010101。如果你使用数字为170的10101010尝试这种方法，你将得到类似的功能，唯一的区别是当你与0 0进行操作时，你会得到数字128（它在二进制中为10000000）。类似的技术被用于各种按位操作的优化，比如使用掩码0x55555555和0xAAAAAAAA计算一个二进制集合中位数的数量（其中0x55=85，0xAA=170）。如果你在Google上搜索这些十六进制代码，你会找到一些有趣的文章。 - Havenard

哇，我从未想到数字85有这么多深度。感谢您的洞察力。 - William Lee

我假设您的意思是0到9之间都包括在内？ - pipe

这绝对是值得参加IOCCC比赛的。 - dgnuff

Answer 1

如果使用小端整数（并假设使用 ASCII 文本、8 位字节和代码需要的所有其他假设），并忽略代码中在现代 C 中技术上错误的所有内容，那么您对“我目前的理解”是正确的。

gets(&n) 将把 A、空格和 B 的 ASCII 值存储到 n 的前 3 个字节中。它还将在第 4 个字节中存储空终止符。将这些 ASCII 值存储到 n 的这些字节中会导致 n 取值 B*256*256 + space*256 + A，其中 B、space 和 A 分别表示相应的 ASCII 值。

256 mod 85 为 1，因此根据模运算的性质，

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

顺便提一下，如果使用4字节大端整数，我们会得到

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

只要我们有4字节的整数，字节序就无所谓了。(更大或更小的整数可能会是个问题；例如，对于8字节的整数，我们需要担心gets没有设置的字节中有什么。)

空格是ASCII 32，数字字符的ASCII值是48加上该数字的值。如果将a和b定义为输入数字的数值(而不是数字字符的ASCII值)，则我们有：

(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

最后两个等式依赖于 a 和 b 取值在 0 到 9 之间这一事实。

- user2357112