(a + (b & 255) & 255)是否与(a + b) & 255相同？

我浏览了一些 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 标题感到抱歉，请随意编辑它。

8668 次浏览
小开
最佳答案

They are the same. Here's a proof:

First note the identity (A + B) mod C = (A mod C + B mod C) mod C

Let's restate the problem by regarding a & 255 as standing in for a % 256. This is true since a is unsigned.

So (a + (b & 255)) & 255 is (a + (b % 256)) % 256

This is the same as (a % 256 + b % 256 % 256) % 256 (I've applied the identity stated above: note that mod and % are equivalent for unsigned types.)

This simplifies to (a % 256 + b % 256) % 256 which becomes (a + b) % 256 (reapplying the identity). You can then put the bitwise operator back to give

(a + b) & 255

completing the proof.

小开

Yes, (a + b) & 255 is fine.

Remember addition in school? You add numbers digit by digit, and add a carry value to the next column of digits. There is no way for a later (more significant) column of digits to influence an already processed column. Because of this, it does not make a difference if you zero-out the digits only in the result, or also first in an argument.

The above is not always true, the C++ standard allows an implementation that would break this.

Such a Deathstation 9000 :-) would have to use a 33-bit int, if the OP meant unsigned short with "32-bit unsigned integers". If unsigned int was meant, the DS9K would have to use a 32-bit int, and a 32-bit unsigned int with a padding bit. (The unsigned integers are required to have the same size as their signed counterparts as per §3.9.1/3, and padding bits are allowed in §3.9.1/1.) Other combinations of sizes and padding bits would work too.

As far as I can tell, this is the only way to break it, because:

  • The integer representation must use a "purely binary" encoding scheme (§3.9.1/7 and the footnote), all bits except padding bits and the sign bit must contribute a value of 2n
  • int promotion is allowed only if int can represent all the values of the source type (§4.5/1), so int must have at least 32 bits contributing to the value, plus a sign bit.
  • the int can not have more value bits (not counting the sign bit) than 32, because else an addition can not overflow.
小开

In positional addition, subtraction and multiplication of unsigned numbers to produce unsigned results, more significant digits of the input don't affect less-significant digits of the result. This applies to binary arithmetic as much as it does to decimal arithmetic. It also applies to "twos complement" signed arithmetic, but not to sign-magnitude signed arithmetic.

However we have to be careful when taking rules from binary arithmetic and applying them to C (I beleive C++ has the same rules as C on this stuff but i'm not 100% sure) because C arithmetic has some arcane rules that can trip us up. Unsigned arithmetic in C follows simple binary wraparound rules but signed arithmetic overflow is undefined behaviour. Worse under some circumstances C will automatically "promote" an unsigned type to (signed) int.

Undefined behaviour in C can be especially insiduous. A dumb compiler (or a compiler on a low optimisation level) is likely to do what you expect based on your understanding of binary arithmetic while an optimising compiler may break your code in strange ways.

So getting back to the formula in the question the equivilence depends on the operand types.

If they are unsigned integers whose size is greater than or equal to the size of int then the overflow behaviour of the addition operator is well-defined as simple binary wraparound. Whether or not we mask off the high 24 bits of one operand before the addition operation has no impact on the low bits of the result.

If they are unsigned integers whose size is less than int then they will be promoted to (signed) int. Overflow of signed integers is undefined behaviour but at least on every platform I have encountered the difference in size between different integer types is large enough that a single addition of two promoted values will not cause overflow. So again we can fall back to the simply binary arithmetic argument to deem the statements equivalent.

If they are signed integers whose size is less than int then again overflow can't happen and on twos-complement implementations we can rely on the standard binary arithmetic argument to say they are equivilent. On sign-magnitude or ones complement implementations they would not be equivilent.

OTOH if a and b were signed integers whose size was greater than or equal to the size of int then even on twos complement implementations there are cases where one statement would be well-defined while the other would be undefined behaviour.

小开

Identical assuming no overflow. Neither version is truly immune to overflow but the double and version is more resistant to it. I am not aware of a system where an overflow in this case is a problem but I can see the author doing this in case there is one.

小开

You already have the smart answer: unsigned arithmetic is modulo arithmetic and therefore the results will hold, you can prove it mathematically...

One cool thing about computers, though, is that computers are fast. Indeed, they are so fast that enumerating all valid combinations of 32 bits is possible in a reasonable amount of time (don't try with 64 bits).

So, in your case, I personally like to just throw it at a computer; it takes me less time to convince myself that the program is correct than it takes to convince myself than the mathematical proof is correct and that I didn't oversee a detail in the specification1:

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

This enumerates through all possible values of a and b in the 32-bits space and checks whether the equality holds, or not. If it does not, it prints the case which didn't work, which you can use as a sanity check.

And, according to Clang: Equality holds.

Furthermore, given that the arithmetic rules are bit-width agnostic (above int bit-width), this equality will hold for any unsigned integer type of 32 bits or more, including 64 bits and 128 bits.

Note: How can a compiler enumerates all 64-bits patterns in a reasonable time frame? It cannot. The loops were optimized out. Otherwise we would all have died before execution terminated.

I initially only proved it for 16-bits unsigned integers; unfortunately C++ is an insane language where small integers (smaller bitwidths than int) are first converted to 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;
}

And once again, according to Clang: Equality holds.

Well, there you go :)

1 Of course, if a program ever inadvertently triggers Undefined Behavior, it would not prove much.

小开

The quick answer is: both expressions are equivalent

  • since a and b are 32-bit unsigned integers, the result is the same even in case of overflow. unsigned arithmetic guarantees this: a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

The long answer is: there are no known platforms where these expressions would differ, but the Standard does not guarantee it, because of the rules of integral promotion.

  • If the type of a and b (unsigned 32 bit integers) has a higher rank than int, the computation is performed as unsigned, modulo 232, and it yields the same defined result for both expressions for all values of a and b.

  • Conversely, If the type of a and b is smaller than int, both are promoted to int and the computation is performed using signed arithmetic, where overflow invokes undefined behavior.

    • If int has at least 33 value bits, neither of the above expressions can overflow, so the result is perfectly defined and has the same value for both expressions.

    • If int has exactly 32 value bits, the computation can overflow for both expressions, for example values a=0xFFFFFFFF and b=1 would cause an overflow in both expressions. In order to avoid this, you would need to write ((a & 255) + (b & 255)) & 255.

  • The good news is there are no such platforms1.

1 More precisely, no such real platform exists, but one could configure a DS9K to exhibit such behavior and still conform to the C Standard.

小开

Lemma: a & 255 == a % 256 for unsigned a.

Unsigned a can be rewritten as m * 0x100 + b some unsigned m,b, 0 <= b < 0xff, 0 <= m <= 0xffffff. It follows from both definitions that a & 255 == b == a % 256.

Additionally, we need:

  • the distributive property: (a + b) mod n = [(a mod n) + (b mod n)] mod n
  • the definition of unsigned addition, mathematically: (a + b) ==> (a + b) % (2 ^ 32)

Thus:

(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

So yes, it is true. For 32-bit unsigned integers.

What about other integer types?

  • For 64-bit unsigned integers, all of the above applies just as well, just substituting 2^64 for 2^32.
  • For 8- and 16-bit unsigned integers, addition involves promotion to int. This int will definitely neither overflow or be negative in any of these operations, so they all remain valid.
  • For signed integers, if either a+b or a+(b&255) overflow, it's undefined behavior. So the equality can't hold — there are cases where (a+b)&255 is undefined behavior but (a+(b&255))&255 isn't.
小开

Yes you can prove it with arithmetic, but there is a more intuitive answer.

When adding, every bit only influences those more significant than itself; never those less significant.

Therefore, whatever you do to the higher bits before the addition won't change the result, as long as you only keep bits less significant than the lowest bit modified.

小开

The proof is trivial and left as an exercise for the reader

But to actually legitimize this as an answer, your first line of code says take the last 8 bits of b** (all higher bits of b set to zero) and add this to a and then take only the last 8 bits of the result setting all higher bits to zero.

The second line says add a and b and take the last 8 bits with all higher bits zero.

Only the last 8 bits are significant in the result. Therefore only the last 8 bits are significant in the input(s).

** last 8 bits = 8 LSB

Also it is interesting to note that the output would be equivalent to

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

As above, only the 8 LSB are significant, but the result is an unsigned int with all other bits zero. The a + b will overflow, producing the expected result.


提交答案