3 ms·
A somewhat common use of XOR is p != q. It is actually an XOR. Another useful way to think of XOR is "either p or q is true, but not both, and not neither."
by toxik 6y ago
A somewhat common use of XOR is p != q. It is actually an XOR.
Another useful way to think of XOR is "either p or q is true, but not both, and not neither."
- bonzini 6y agoCompilers can optimize "a != b" to "a xor b" if they know that both operands are 0 or 1. There are crazy many expression rewriting rules.
- dan-robertson 6y agoThey don’t need to be 0 or 1. We already know that a ^ a = 0, a ^ 0 = a, and a ^ (b ^ c) = (a ^ b) ^ c, so we must have a ^ b = 0 only when a = b. Therefore in the C convention where 0 means false, a ^ b = not (a = b) = (a!=b) (this equality only holds for expressions that are going straight into a Boolean operation (or test in eg an if statement), as a!=b should always evaluate to 0 or 1. The compiler may use this by xoring a and b and then jumping if the zero flag was set.
- bonzini 6y ago> (this equality only holds for expressions that are going straight into a Boolean operation Right, though that's more commonly turned into just a cmp instruction (a subtraction). However, if the result is assigned to a variable, on x86 "a != b" would be two or three instructions (possibly clearing a register because setne takes an 8-bit register operand only, and then a cmp/setne pair). Instead the xor would be one instruction, or two if a mov is needed.
- globular-toast 6y ago> Another useful way to think of XOR is "either p or q is true, but not both, and not neither." That's literally what eXclusive OR means. This should be the first way to think about it.
- toxik 6y agoI think most people think of XOR as “difference of bits”, which it is.
- dan-robertson 6y agoFWIW, I mostly think of it as addition in Z_2^n.
- globular-toast 6y agoThat is more traditional. It's addition without carry.
- randomswede 6y agoAlthough in Z_2^n, "addition without carry" and "subtraction without carry" are the same operation.