Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.9k views
in Technique[技术] by (71.8m points)

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

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
");
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...