Martin - 2 months ago 19

C++ 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`

`b`

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.