Why is (a | b ) equivalent to a - (a & b) + b?

Question

I was looking for a way to do a BITOR() with an Oracle database and came across a suggestion to just use BITAND() instead, replacing BITOR(a,b) with a + b - BITAND(a,b).I tested it by hand a few times and verified it seems to work for all binary numbers I could think of, but I can't think out quick mathematical proof of why this is correct. Could somebody enlighten me?

Answer 1

This is, essentially, a form of the principle of inclusion-exclusion (https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle). For each bit, there are 4 cases:

1. It's 1 in a, 0 in b (this bit should be 1 in a | b). Then the corresponding bit in a & b will be 0, so we end up with 1-0+1=1.
2. It's 1 in both a and b (this bit should be 1 in a | b). Then the corresponding bit in a & b will be 1, so we end up with 1-1+1=1.
3. It's 0 in a, 1 in b (this bit should be 1 in a | b). Then the corresponding bit in a & b will be 0, so we end up with 0-0+1=1.
4. It's 0 in both a and b (this bit should be 0 in a | b). Then the corresponding bit in a & b will be 0, so we end up with 0-0+0=0.

Note that in no case do we end up with a result that would require a carry bit, so the operation is truly bitwise. No bit will affect any other bit.

Answer 2

Take a look at this crude drawing I've made to help conceptualize this (this is a google drive link): https://urlzs.com/AGdXp. Suppose we have 2 domains A and B which we represent with a Venn diagram. The green area is A∪B (read as "a union b") which contain objects that belong to set A or set B. The yellow area is A∩B (read as "a intersection b") which contains objects that belong to set A and set B. Using this graphical approach, it logically follows that A∪B = A + B - A∩B because the green area can be found by adding the area of A and B and subtracting the yellow area. This applies to your situation assuming that | is the xor operator which is equivalent to the union operator.