（（a +（b＆255））＆255）与（（a + b）＆255）相同吗？
我正在浏览一些C ++代码，发现这样的东西：
(a + (b & 255)) & 255 双烦恼我，所以我想到：
(a + b) & 255
（ a和b是32位无符号整数）
我很快写了一个testing脚本（JS）来证实我的理论：
for (var i = 0; i < 100; i++) { var a = Math.ceil(Math.random() * 0xFFFF), b = Math.ceil(Math.random() * 0xFFFF); var expr1 = (a + (b & 255)) & 255, expr2 = (a + b) & 255; if (expr1 != expr2) { console.log("Numbers " + a + " and " + b + " mismatch!"); break; } }
虽然脚本证实了我的假设（两个操作都是平等的），但我仍然不相信它，因为1） 随机和2）我不是math家， 我不知道我在做什么 。
另外，对于Lisp-y标题感到抱歉。 随意编辑它。
他们是一样的。 这是一个certificate：
首先注意身份(A + B) mod C = (A mod C + B mod C) mod C
让我们通过a & 255入a % 256重申这个问题。 因为a是无符号的，所以这是真的。
所以(a + (b & 255)) & 255是(a + (b % 256)) % 256
这与(a % 256 + b % 256 % 256) % 256 （我已经应用了上述身份：注意mod和%对于无符号types是等效的）。
这简化为(a % 256 + b % 256) % 256 ，变成(a + b) % 256 （重新应用身份）。 然后你可以把这个按位运算符放回去
(a + b) & 255
完成certificate。
在位置加法，减法和乘法中，input的更多有效数字不会影响结果的低位数字。 这与二进制算术一样适用于十进制算术。
然而，我们必须要小心，从二进制算术的规则，并将它们应用到C（我相信C + +有这个东西相同的规则，但我不是100％肯定），因为Calgorithm有一些神秘的规则，可以让我们向上。 C中的无符号算术遵循简单的二元环绕规则，但是有符号算术溢出是未定义的行为。 更糟的是，在某些情况下，C会自动将一个无符号types“提升”为（signed）int。
在C中未定义的行为可能特别的困难。 愚蠢的编译器（或低优化级别的编译器）可能会根据您对二进制算术的理解做你期望的事情，而优化编译器可能会以奇怪的方式破坏你的代码。
所以回到问题公式的等式取决于操作数types。
如果它们是无符号整数，其大小大于或等于int的大小，那么加法运算符的溢出行为就被定义为简单的二进制包装。 在加法操作之前是否屏蔽掉一个操作数的高24位对结果的低位没有影响。
如果它们的大小小于int无符号整数，那么它们将被提升为（signed） int 。 有符号整数的溢出是未定义的行为，但至less在每个平台上，我遇到了不同整数types之间的大小差异足够大，以致一个添加两个提升值不会导致溢出。 所以我们可以再次回到简单的二元算术论证来认为相同的陈述。
如果它们是大小小于int的有符号整数，那么再次溢出就不会发生，而在二进制补码实现中，我们可以依靠标准二进制算术参数来表示它们是等价的。 在符号级别或补码实现方面，它们不会是等价的。
OTOH如果a和b是大小大于或等于int大小的有符号整数，那么即使在二进制补码实现中，也有一种情况是一个语句可以很好地定义，而另一个则是未定义的行为。
引理： a & 255 == a % 256表示无符号a 。
无符号a可以重写为m * 0x100 + b一些无符号的m ， b ， 0 <= b < 0xff ， 0 <= m <= 0xffffff 。 从两个定义可以得出a & 255 == b == a % 256 。
另外，我们需要：
- 分布性质：
(a + b) mod n = [(a mod n) + (b mod n)] mod n - 无符号加法的定义如下：
(a + b) ==> (a + b) % (2 ^ 32)
从而：
(a + (b & 255)) & 255 = ((a + (b & 255)) % (2^32)) & 255 // def'n of addition = ((a + (b % 256)) % (2^32)) % 256 // lemma = (a + (b % 256)) % 256 // because 256 divides (2^32) = ((a % 256) + (b % 256 % 256)) % 256 // Distributive = ((a % 256) + (b % 256)) % 256 // a mod n mod n = a mod n = (a + b) % 256 // Distributive again = (a + b) & 255 // lemma
所以是的，这是真的。 对于32位无符号整数。
其他整数types呢？
- 对于64位无符号整数，上述全部也适用，只需用
2^64代替2^32。 - 对于8位和16位无符号整数，加法涉及提升为
int。 这个int在任何这些操作中肯定不会溢出或者是负面的，所以它们都是有效的。 - 对于有符号整数，如果
a+b或a+(b&255)溢出，那么这是未定义的行为。 所以平等不能成立 – 有(a+b)&255是未定义行为的情况，但是(a+(b&255))&255不是。
是的， (a + b) & 255是好的。
记得在学校补充？ 您可以逐位数字添加数字，并将进位值添加到下一列数字。 没有办法让后面的（更重要的）数字列影响已处理的列。 正因为如此，如果您仅在结果中清零数字，或者也首先在参数中清零，则没有任何区别。
上述情况并不总是如此，C ++标准允许一个实现会破坏这个。
这样的死亡站9000 ： – ）将不得不使用一个33位int ，如果OP意味着unsigned short “32位无符号整数”。 如果是unsigned int ，那么DS9K将不得不使用一个32位的int和一个带填充位的32位unsigned int 。 （无符号整数必须和§3.9.1/ 3中的符号相同，填充位在§3.9.1/ 1中允许）。其他尺寸和填充位的组合也可以。
据我所知，这是打破它的唯一方法，因为：
- 整数表示必须使用“纯二进制”编码scheme（§3.9.1/ 7和脚注），除填充位和符号位之外的所有位必须贡献值2 n
- 只有当
int可以表示源types的所有值（§4.5/ 1）时，才允许int提升，所以int必须至less有32位贡献值，加上一个符号位。 -
int不能有比32更多的值（不包括符号位），否则加法不能溢出。
你已经有了聪明的答案：无符号算术是模算术，因此结果将成立，你可以certificate它math…
电脑的一个很酷的事情是电脑速度很快。 事实上，它们速度如此之快以至于在合理的时间内枚举所有有效的32位组合是可能的（不要尝试64位）。
所以，就你而言，我个人喜欢把它扔在电脑上， 需要我花费更less的时间来说服自己，程序是正确的，而不是说服自己，而不是mathcertificate是正确的，我没有监督规范1中的细节：
#include <iostream> #include <limits> int main() { std::uint64_t const MAX = std::uint64_t(1) << 32; for (std::uint64_t i = 0; i < MAX; ++i) { for (std::uint64_t j = 0; j < MAX; ++j) { std::uint32_t const a = static_cast<std::uint32_t>(i); std::uint32_t const b = static_cast<std::uint32_t>(j); auto const champion = (a + (b & 255)) & 255; auto const challenger = (a + b) & 255; if (champion == challenger) { continue; } std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n"; return 1; } } std::cout << "Equality holds\n"; return 0; }
这列举了32位空间中a和b所有可能的值，并检查等式是否成立。 如果没有，它打印没有工作的情况下，你可以使用它作为一个健全的检查。
而且， 根据铿 ： 平等持有 。
此外，考虑到算术规则是位宽不可知的（高于int位宽），这种相等性将适用于32位或更多的任何无符号整数types，包括64位和128位。
注意：编译器如何在合理的时间范围内枚举所有64位的模式？ 这不可以。 循环被优化了。 否则，我们都会死在执行终止之前。
我最初只certificate了它为16位无符号整数; 不幸的是C ++是一个疯狂的语言，其中小整数（比int小的位宽）首先被转换为int 。
#include <iostream> int main() { unsigned const MAX = 65536; for (unsigned i = 0; i < MAX; ++i) { for (unsigned j = 0; j < MAX; ++j) { std::uint16_t const a = static_cast<std::uint16_t>(i); std::uint16_t const b = static_cast<std::uint16_t>(j); auto const champion = (a + (b & 255)) & 255; auto const challenger = (a + b) & 255; if (champion == challenger) { continue; } std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n"; return 1; } } std::cout << "Equality holds\n"; return 0; }
再次， 根据铿 ： 平等认为 。
那么，你去:)
1 当然，如果一个程序无意中触发了未定义的行为，那么这个行为就不会有太大的改变。
快速的答案是：两个expression式是等价的
- 由于
a和b是32位无符号整数，所以即使在溢出的情况下结果也是一样的。 无符号算术保证这一点： 无法用结果的无符号整数types表示的结果被减去一个大于可由结果types表示的最大值的数字。
漫长的回答是：由于整体推广的规则，没有这些expression方式不同的已知平台，但标准并不能保证。
-
如果
a和b（无符号32位整数）的types比int有更高的等级，则计算以无符号模数执行，模数为2 32 ，对于a和b所有值，这两个expression式的定义结果相同。 -
相反，如果
a和b的types小于int，则将它们都提升为int并使用带符号的算术执行计算，其中溢出会调用未定义的行为。-
如果
int至less有33个数值位，上面的expression式都不能溢出，所以结果是完美定义的，并且对于这两个expression式都有相同的值。 -
如果
int正好有32个数值位，则两个expression式的计算都会溢出，例如a=0xFFFFFFFF和b=1会导致两个expression式的溢出。 为了避免这种情况，你需要写((a & 255) + (b & 255)) & 255。
-
-
好消息是没有这样的平台1 。
1更确切地说，没有这样真实的平台存在，但是可以configurationDS9K来performance出这样的行为，并且仍然符合C标准。
假设没有溢出相同。 这两个版本都没有真正的免疫溢出，但双版本更耐受。 我不知道在这种情况下溢出的系统是一个问题，但我可以看到作者这样做，如果有一个。
是的，你可以用算术来certificate它，但是有一个更直观的答案。
join时，每一位只影响比自己更重要的那些; 从来没有那么重要。
因此，无论您在添加之前对较高位进行何种操作，都不会改变结果，只要您只保留比最低位更低的位。
certificate是微不足道的，作为读者的练习
但是要真正将这个合法化为一个答案，你的第一行代码就是把b **的最后8位（ b所有高位设为0）加到a ，然后只取结果的最后8位将所有高位设置为零。
第二行表示添加a和b并取所有高位为零的最后8位。
结果中只有最后8位是重要的。 因此在input中只有最后8位是重要的。
** 最后8位 = 8 LSB
另外值得注意的是输出将相当于
char a = something; char b = something; return (unsigned int)(a + b);
如上所述，只有8个LSB是有意义的，但结果是一个unsigned int ，其他所有位都是零。 a + b将溢出，产生预期的结果。
