我正在浏览一些C++代码,发现这样的东西:
(a + (b & 255)) & 255
双重和我生气,所以我想到:
(a + b) & 255
(a并且b是32位无符号整数)
我很快写了一个测试脚本(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)我不是数学家,我不知道我在做什么.
另外,抱歉Lisp-y标题.随意编辑它.
Bat*_*eba 78
他们是一样的.这是一个证明:
首先要注意身份 (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并且%对于无符号类型是等效的.)
这简化了对(a % 256 + b % 256) % 256成为(a + b) % 256(重新应用标识).然后,您可以将按位运算符放回去
(a + b) & 255
完成证明.
plu*_*ash 21
在位置加法,减法和乘法中,输入的更多有效数字不会影响结果的较低有效位.这适用于二进制算术,与十进制算术一样多.
但是,从二进制算术中获取规则并将它们应用于C时我们必须要小心(我相信C++在这个问题上与C具有相同的规则,但我不是100%肯定)因为C算术有一些可以使我们感到震惊的神秘规则起来.C中的无符号算术遵循简单的二进制环绕规则,但带符号的算术溢出是未定义的行为.更糟糕的是,在某些情况下,C会自动将"无符号"类型"提升"为(signed)int.
C中未定义的行为可能特别隐蔽.根据您对二进制算术的理解,一个愚蠢的编译器(或低优化级别的编译器)可能会按照您的预期执行操作,而优化编译器可能会以奇怪的方式破坏您的代码.
因此,回到问题中的公式,等效性取决于操作数类型.
如果它们是大小大于或等于大小的无符号整数,int则加法运算符的溢出行为被明确定义为简单的二进制环绕.在加法运算之前是否屏蔽掉一个操作数的高24位对结果的低位没有影响.
如果它们是大小小于的无符号整数,int则它们将被提升为(已签名)int.有符号整数的溢出是未定义的行为,但至少在我遇到的每个平台上,不同整数类型之间的大小差异足够大,只需添加两个提升值就不会导致溢出.因此,我们可以再次回到简单的二进制算术参数来认为语句是等价的.
如果它们是大小小于int的有符号整数,则再次溢出不会发生,并且在二进制补码实现上,我们可以依赖标准二进制算术参数来表示它们是等效的.在符号幅度或补码实现上,它们不是等价的.
OTOH if a和b者是有符号整数,其大小大于或等于int的大小,那么即使在二进制补码实现中,也有一种语句定义明确而另一种语句是未定义行为的情况.
Bar*_*rry 20
引理: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位无符号整数.
其他整数类型怎么样？
2^64了2^32.int.int在任何这些操作中,这肯定既不会溢出也不会消极,因此它们都保持有效.a+b或a+(b&255)溢出,这是不确定的行为.所以平等不能成立 - 有些情况(a+b)&255是未定义的行为,但事实(a+(b&255))&255并非如此.ala*_*ain 17
是的,(a + b) & 255很好.
还记得在学校加分吗？您逐位添加数字,并将进位值添加到下一列数字.后面的(更重要的)数字列无法影响已处理的列.因此,如果仅在结果中将数字清零,或者在参数中首先清零,则没有区别.
上述情况并非总是如此,C++标准允许实现破坏这一点.
如果OP意味着"32位无符号整数" ,那么这样的Deathstation 9000 :- )必须使用33位.如果是这样的话,DS9K必须使用32位,32位和填充位.(无符号整数必须与符合§3.9.1/ 3的有符号整数具有相同的大小,并且在§3.9.1/ 1中允许填充位.)其他大小和填充位组合也可以工作.intunsigned shortunsigned intintunsigned int
据我所知,这是打破它的唯一方法,因为:
int可以表示源类型的所有值(§4.5/ 1)时才允许int promote,因此int必须至少有32位对该值有贡献,加上符号位.int不能有更多的值的比特(不包括符号位)超过32,因为其他的加成不能溢出.Mat*_* M. 14
你已经有了明智的答案:无符号算术是模运算,因此结果将成立,你可以用数学证明它...
然而,关于计算机的一个很酷的事情是计算机很快.实际上,它们如此之快以至于在合理的时间内枚举所有有效的32位组合(不要尝试使用64位).
所以,在你的情况下,我个人喜欢把它扔在电脑上; 我花了更少的时间来说服自己这个程序是正确的,而不是说服自己,而不是数学证明是正确的,而且我没有监督规范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;
}
此枚举通过的所有可能值a,并b在32位空间并检查平等是否成立,或没有.如果没有,则打印不起作用的外壳,您可以将其用作完整性检查.
并且,据Clang说:平等成立.
此外,假设算术规则是位宽度不可知的(高于int位宽),则该等式将适用于32位或更多的无符号整数类型,包括64位和128位.
注意:编译器如何在合理的时间范围内枚举所有64位模式？这不可以.循环被优化了.否则我们都会在执行终止前死亡.
我最初只用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;
}
再一次,据Clang说:平等成立.
好吧,你去:)
1 当然,如果某个程序无意中触发了未定义的行为,那么它就不会有太大的影响.
简单的回答是：两个表达式是等价的
a和b是 32 位无符号整数，因此即使在溢出的情况下结果也是相同的。无符号算术保证了这一点：无法由结果无符号整数类型表示的结果会以比结果类型可以表示的最大值大 1 的数为模进行缩减。长的答案是：没有已知的平台会导致这些表达方式有所不同，但由于积分提升的规则，标准并不保证这一点。
a如果和的类型b（无符号 32 位整数）的秩高于int，则计算将以无符号、模 2 32的形式执行，并且对于a和的所有值，两个表达式都会产生相同的定义结果b。
a相反，如果和 的类型b小于int，则两者都会提升为int并使用有符号算术执行计算，其中溢出会调用未定义的行为。
如果int至少有 33 个值位，则上述两个表达式都不会溢出，因此结果是完美定义的，并且两个表达式的值相同。
如果正好有 32 个值位，则两个表达式（例如值）的int计算可能会溢出，并且会导致两个表达式都溢出。为了避免这种情况，您需要编写.a=0xFFFFFFFFb=1((a & 255) + (b & 255)) & 255
好消息是没有这样的平台1。
1更准确地说，不存在这样的真实平台，但可以配置 DS9K以表现出这种行为，并且仍然符合 C 标准。