Martin Martin - 16 days ago 11
C++ Question

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

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

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.