((a + (b & 255)) & 255) 和 ((a + b) & 255) 相同吗?(涉及 IT 技术)

92
我正在浏览一些C++代码,发现了这样的内容:
(a + (b & 255)) & 255

双重AND让我感到烦恼,所以我想到了:

(a + b) & 255

(ab都是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。随意编辑。

4
那是什么语言的脚本?Math.random()在[0,1)范围内返回整数还是双精度浮点数?我认为你的脚本(就我所知)根本没有反映出你提出的问题。 - Brick
7
C/C++代码是什么?它们是不同的编程语言。 - Weather Vane
14
你无法在JS中复制你试图测试的行为。这就是为什么每个人都只关心你的语言选择。JS没有强类型,并且答案在C/C++变量类型上至关重要。鉴于你提出的问题,JS是完全没有意义的。 - Brick
4
@WeatherVane 这基本上是伪代码,使用了Javascript函数名称。他的问题是关于C和C++中无符号整数上&+的行为。 - Barmar
11
请记住,“我编写了一个测试程序,对于所有可能的输入都得到了我期望的答案”并不能保证某个程序的行为符合您的期望。未定义的行为可能会非常棘手,即在你确信代码正确之后才给出意外的结果。 - user1084944
显示剩余19条评论
9个回答

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

证毕。


81
这是一个数学证明,不考虑溢出的可能性。考虑 A=0xFFFFFFFF, B=1, C=3。第一个等式不成立。(对于无符号算术来说,溢出不会成为问题,但它与此有些不同。) - AlexD
4
实际上,(a + (b & 255)) & 255(a + (b % 256)) % N % 256 相同,其中 N 是最大无符号值加一。后面的公式应该被理解为数学整数的算术运算。 - user1084944
17
像这样的数学证明并不适合用来证明整数在计算机体系结构上的行为。 - Jack Aidley
26
当正确使用时,它们是恰当的(但一个人由于忽略溢出而没有正确使用)。 - user1084944
3
-1是因为这个证明是错误的。如果考虑到a+b是对2的32次方取模计算,那么可以正确地写出来。 - R.. GitHub STOP HELPING ICE
显示剩余7条评论

21
在无符号数的位置加法、减法和乘法中生成无符号结果时,输入的更高位数字不会影响结果的较低位数字。这适用于二进制算术和十进制算术。它也适用于“二进制补码”有符号算术,但不适用于符号-幅度有符号算术。
然而,在从二进制算术中取规则并应用于C语言时,我们必须小心(我认为C ++在这方面有与C相同的规则,但我不确定),因为C算术具有一些可以使我们失误的神秘规则。 C中的无符号算术遵循简单的二进制环绕规则,但有符号算术溢出是未定义的行为。更糟糕的是,在某些情况下,C将自动将无符号类型提升为(有符号的)int。
C中的未定义行为可能特别难以察觉。愚蠢的编译器(或低优化级别的编译器)可能会根据您对二进制算术的理解来做您期望的事情,而优化编译器可能会以奇怪的方式破坏您的代码。
因此,回到问题中的公式,等价性取决于操作数类型。
如果它们是无符号整数,其大小大于或等于int的大小,则加法运算符的溢出行为是定义良好的,作为简单的二进制环绕。将其相加之前是否屏蔽一个操作数的高24位对结果的低位没有影响。
如果它们是无符号整数,其大小小于int ,则它们将提升为(有符号的)int 。有符号整数溢出是未定义的行为,但至少在我遇到的每个平台上,不同整数类型之间的差异足够大,以至于两个提升值的单个加法不会导致溢出。因此,我们可以退回到简单的二进制算术论证来认为这些语句是等效的。
如果它们是大小小于int的有符号整数,则再次不能发生溢出,并且在二进制补码实现中,我们可以依赖于标准的二进制算术论证来说它们是相等的。在符号-幅度或ones complement实现中,它们将不是等价的。

然而,如果ab是有符号整数,其大小大于或等于int类型的大小,则即使在二进制补码实现中,有些情况下一个语句行为将被定义良好,而另一个则会导致未定义的行为。


21

引理: 对于无符号的 a,有 a & 255 == a % 256

无符号的 a 可以被重写为 m * 0x100 + b,其中 mb 都是无符号整数,0 <= b < 0xff0 <= 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位无符号整数。


其他整数类型呢?

  • 对于64位无符号整数,所有上述内容同样适用,只需将 2^64 替换为 2^32 即可。
  • 对于8位和16位无符号整数,加法涉及到提升为 int。在任何这些操作中,这个 int 都绝不会溢出或为负数,所以它们仍然有效。
  • 对于有符号整数,如果 a+ba+(b&255) 溢出,那么其行为未定义。因此,等式不能成立——存在情况使得 (a+b)&255 的行为未定义,但 (a+(b&255))&255 的行为是定义的。

17

是的,(a + b) & 255 是可以的。

还记得在学校里做加法吗?你逐位相加,并将进位值添加到下一列数字中。后面(更重要的)数字列没有办法影响已经处理过的数字列。因此,在结果中仅将数字清零,或者在参数中首先将数字清零并不重要。


然而上述并不总是正确的,C++标准允许破坏这个规则的实现。

这样一个Deathstation 9000::-)如果OP指的是 "32位无符号整数",那么它必须使用33位的 int;如果意思是unsigned int,DS9K就必须使用32位的int和带有填充位的32位unsigned int 。(根据 §3.9.1/3,无符号整数需要与其有符号的对应类型保持相同的大小,根据 §3.9.1/1,允许使用填充位。)其他大小和填充位的组合也可以工作。

据我所知,这是破坏规则的唯一方法,因为:

  • 整数表示必须使用“纯二进制”编码方案(§3.9.1/7和脚注),除了填充位和符号位之外,所有位必须贡献2n的值。
  • 仅当int能够表示源类型的所有值时才允许进行 int 提升(§4.5/1),因此int必须至少有32位对值有贡献,加上一个符号位。
  • int 不能有比32更多的值位(不包括符号位),否则加法会导致溢出。

  • 2
    除了加法之外,还有许多其他操作,其中高位的垃圾不会影响您感兴趣的低位结果。请参见关于二进制补码的此问答,它以x86汇编语言为用例,但也适用于任何情况下的无符号二进制整数。 - Peter Cordes
    2
    虽然匿名投票是每个人的权利,但我总是很感激评论,因为它是学习的机会。 - alain
    2
    这是我认为迄今为止最容易理解的答案/论点。在二进制中,加法/减法中的进位/借位仅从低位向高位(从右到左)传播,与十进制相同。我不知道为什么有人会对此进行反对投票。 - Peter Cordes
    1
    @Bathsheba:CHAR_BIT不一定要为8。但是在C和C++中,无符号类型必须表现为某个位宽的普通二进制整数。我认为这要求UINT_MAX为2^N-1。(N甚至可能不需要是CHAR_BIT的倍数,我忘了,但我相当确定标准要求在某个2的幂次下进行模运算)。我认为唯一可能出现奇怪情况的方式是通过将其提升为一个有足够宽度来容纳ab但不足以容纳所有情况下的a+b的有符号类型。 - Peter Cordes
    2
    @Bathsheba:是的,幸运的是,C作为可移植汇编语言在无符号类型上确实大多数情况下都能正常工作。即使是故意敌对的C实现也无法破坏它。只有在有符号类型中,C中真正可移植的位操作才会变得非常糟糕,而Deathstation 9000确实可以破坏你的代码。 - Peter Cordes
    显示剩余10条评论

    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;
    }
    

    这个程序枚举了32位空间中所有可能的ab的值,并检查是否成立。如果不成立,它会打印出未能成功的情况,你可以用作合理性检查。

    而且,根据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 当然,如果程序意外触发了未定义行为,这并不能证明什么。


    1
    你说用32位值很容易实现,但实际上使用16位的... :D - Willi Mentzel
    1
    @WilliMentzel:这是一个有趣的评论。我最初想说,如果它可以与16位一起工作,那么在32位、64位和128位下它也会以相同的方式工作,因为标准对于不同的位宽没有特定的行为……然而我记得它实际上对于比“int”小的位宽是有特定规则的:小整数首先转换为“int”(一个奇怪的规则)。所以我实际上需要用32位来进行演示(之后它会扩展到64位、128位等)。 - Matthieu M.
    2
    由于您无法评估所有(4294967296-1)*(4294967296-1)个可能的结果,您会以某种方式进行缩减吗?在我看来,如果您采用这种方法,MAX应该是(4294967296-1),但像您所说的那样,它永远不会在我们的有生之年内完成...因此,毕竟我们无法在实验中展示平等,至少不像您描述的那样。 - Willi Mentzel
    1
    仅在一个二进制补码实现上进行测试并不能证明它可以适用于符号-幅值或一的补码与Deathstation 9000类型宽度。例如,一个狭窄的无符号类型可能会提升为一个17位的int,它可以表示每个可能的uint16_t,但是a+b可能会溢出。这只是对比int更窄的无符号类型的问题;C要求unsigned类型是二进制整数,因此环绕发生在2的幂次方模下 - Peter Cordes
    1
    @PeterCordes:但至少如果你有一个测试,那么找出问题仍然比在垃圾桶里的数学证明草图上容易得多(特别是在使用-fsanitize=undefined这样的工具链时)。另外...可移植性是一回事,但有时候没有意义。面对现实吧,这些天,非8位字节、非1/2/4/8字节整数和非二补表示的架构已经很“奇特”了。 - Matthieu M.
    显示剩余9条评论

    5
    快速回答是:这两个表达式是等价的。
    由于a和b都是32位无符号整数,即使出现溢出情况,结果也是相同的。无符号算术保证了这一点:不能用结果无法表示的无符号整数类型被减少模比结果类型大的最大值多一个数字。 长答案是:没有已知的平台会有这些表达式不同的情况,但标准没有保证它,因为整数提升的规则。
    • 如果ab(无符号32位整数)的类型比int更高,则计算将作为无符号值进行,模232,并且对于所有ab的值,两个表达式都产生相同的定义结果。

    • 相反,如果ab的类型小于int,则两者都会提升为int,并使用有符号算术执行计算,其中溢出会调用未定义的行为。

      • 如果int至少具有33个值位,则上述任何一个表达式都不会溢出,因此结果完全定义,并且两个表达式具有相同的值。

      • 如果int恰好具有32个值位,则两个表达式都可能溢出,例如值a=0xFFFFFFFFb=1会导致两个表达式都溢出。为了避免这种情况,您需要编写((a & 255) + (b & 255)) & 255

    • 好消息是没有这样的平台1


    更准确地说,不存在这样的实际平台,但可以配置 DS9K 以展示这种行为,并仍符合 C 标准。

    3
    你的第二个子项目要求 (1) aint 小 (2) int 有32个值位 (3) a=0xFFFFFFFF。这些条件不可能同时成立。 - Barry
    2
    @Barry:似乎符合要求的一个情况是33位的int,其中有32个值位和一个符号位。 - Ben Voigt

    2

    假设没有溢出,两个版本是相同的。但是,这两个版本都不会真正免疫溢出,但双精度版本更加抵抗溢出。据我所知,在这种情况下溢出不会成为问题,但如果有一种情况,作者可能会采取这种方式。


    1
    OP指定:*(a和b是32位无符号整数)。除非int宽度为33位,否则即使在溢出的情况下结果也是相同的**。无符号算术保证了这一点:不能由结果无符号整数类型表示的结果将对比结果类型能够表示的最大值多1的数字取模。* - chqrlie

    2

    是的,您可以通过算术证明它,但有一个更直观的答案。

    在加法中,每个位只影响比它本身更重要的位;从来不会影响那些不太重要的位。

    因此,在加法前对高位进行任何操作都不会改变结果,只要保留比最低位修改的位不太重要即可。


    0

    证明是微不足道的,留给读者作为练习

    但是为了将其正式化为答案,你的第一行代码说要取b的最后8位(所有更高位的b都设置为零),并将其加到a上,然后只取结果的最后8位,将所有更高位设置为零。

    第二行说要将ab相加,并取最后8位,所有更高位都为零。

    结果中只有最后8位是重要的。因此,输入中只有最后8位是重要的。

    ** 最后8位 = 8个LSB

    另外值得注意的是,输出等同于

    char a = something;
    char b = something;
    return (unsigned int)(a + b);
    

    如上所述,只有8个最低有效位是重要的,但结果是一个unsigned int,所有其他位都为零。 a + b将溢出,产生预期的结果。


    不会的。Char数学运算会被视为int,而char可以是有符号的。 - Antti Haapala -- Слава Україні

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接