Martin - 7 months ago 51
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.

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.

Source (Stackoverflow)