Regarding the identity, XOR is a kind of addition, without carry.
101
^ 011
-----
= 110
We added 1 + 1, to get 10. We put down a 0, but didn't carry the 1.
The carry is separately calculated using AND:
101
& 011
-----
001 <- carry out from LSB.
Of course the carry is carried so we have to shift it left: 010. We can just add the carry afterward (using regular addition which will propagate additional carries not calculated by the AND, like the one from the second digit.
This works only for non-negative integers, right? If there's a sign bit, that won't work right with XOR, if one operand is negative then the sign bit comes out negative.
Duh, of course that's how multiplication works. If one operand is negative, so will be the sign bit of the result. If both are negative, then the result should be and does come out positive, as the sign bit XORs to 0 and so do all adjacent bits that are 1 in both operands.
The carry is separately calculated using AND:
Of course the carry is carried so we have to shift it left: 010. We can just add the carry afterward (using regular addition which will propagate additional carries not calculated by the AND, like the one from the second digit.Thus the identity: