Is ((a + (b & 255)) & 255) the same as ((a + b) & 255)?

Question

I was browsing some C++ code, and found something like this:

(a + (b & 255)) & 255 

The double AND annoyed me, so I thought of:

(a + b) & 255 

(a and b are 32-bit unsigned integers)

I quickly wrote a test script (JS) to confirm my theory:

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

While the script confirmed my hypothesis (both operations are equal), I still don't trust it, because 1) random and 2) I'm not a mathematician, I have no idea what am I doing.

Also, sorry for the Lisp-y title. Feel free to edit it.

Answer 1

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.

Answer 2

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.