bit manipulation - Why is the sum of bitwise AND and bitwise XOR equal to bitwise OR?

Question

Is there a reason why this happens?

#include <stdio.h>

void main() {
    int i, j; //Takes i as 0 with short

    printf("Enter two integers: ");
    scanf("%d %d", &i, &j);

    printf("
%d & %d = %d
", i, j, (i & j));
    printf("
%d ^ %d = %d
", i, j, (i ^ j));
    printf("
%d | %d = %d
", i, j, (i | j));

    if ((i | j) == (i & j) + (i ^ j))
        printf("
YES
");
    else
        printf("
NO
");
}

Answer 1

First note that i & j and i ^ j are disjoint: if a bit is set in one of them, the corresponding bit is necessarily reset in the other. That's a consequence of the truth tables of AND and XOR. AND has only a single row with a 1 in it, and XOR has a 0 in that row, so they're never simultaneously both 1.

That means we can forget about the special complications of addition (there is no carry, which makes addition purely bitwise: equivalent to both OR and XOR), and analyze this expression as if we were dealing with just booleans.

One way to look at it is that i & j exactly compensates for the case that i ^ j does not cover. If you write out the truth tables: (only 1 bit shown)

i j i&j i^j (i&j)|(i^j)
0 0  0   0       0
0 1  0   1       1
1 0  0   1       1
1 1  1   0       1

The last column has values identical to i | j.