Kaitlyn R. answered • 05/24/19

Adjunct Professor in Computer Science

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:

- 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.
- 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.
- 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.
- 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.