Imagine you have two binary numbers: a
and b
. And let's say that these number never have 1 in the same bit at the same time, i.e. if a
has 1 in some bit, the b
always has 0 in the corresponding bit. And in other direction, if b
has 1 in some bit, then a
always has 0 in that bit. For example
a = 00100011
b = 11000100
This would be an example of a
and b
satisfying the above condition. In this case it is easy to see that a | b
would be exactly the same as a + b
.
a | b = 11100111
a + b = 11100111
Let's now take two numbers that violate our condition, i.e. two numbers have at least one 1 in some common bit
a = 00100111
b = 11000100
Is a | b
the same as a + b
in this case? No
a | b = 11100111
a + b = 11101011
Why are they different? They are different because when we +
the bit that has 1 in both numbers, we produce so called carry: the resultant bit is 0, and 1 is carried to the next bit to the left: 1 + 1 = 10
. Operation |
has no carry, so 1 | 1
is again just 1.
This means that the difference between a | b
and a + b
occurs when and only when the numbers have at least one 1 in common bit. When we sum two numbers with 1 in common bits, these common bits get added "twice" and produce a carry, which ruins the similarity between a | b
and a + b
.
Now look at a & b
. What does a & b
calculate? a & b
produces the number that has 1 in all bits where both a
and b
have 1. In our latest example
a = 00100111
b = 11000100
a & b = 00000100
As you saw above, these are exactly the bits that make a + b
differ from a | b
. The 1 in a & b
indicate all positions where carry will occur.
Now, when we do a - (a & b)
we effectively remove (subtract) all "offending" bits from a
and only such bits
a - (a & b) = 00100011
Numbers a - (a & b)
and b
have no common 1 bits, which means that if we add a - (a & b)
and b
we won't run into a carry, and, if you think about it, we should end up with the same result as if we just did a | b
a - (a & b) + b = 11100111