5

While many higher level languages have bitwise (exclusive or) and bitwise (exclusive and), for instance C, C++, Java, etc. I'm curious why the ( vastly more useful ) logical short-circuit operators don't have this functionality? Is it simply due to the capacity of being able to concatenate logic through use of "not"?

This question is mainly to do with the language design considerations....

Improve this question
15
  • 12
    You can't short circuit XOR.
    – user7043
    Mar 30, 2014 at 13:37
  • 1
    @delnan Yes: hence the question
    – Stumbler
    Mar 30, 2014 at 13:38
  • 10
    @Duncan I meant: The XOR operation can't possibly be implemented to short circuit; regardless of the value for the first operand, you always need the value of the second operand to determine the result. 0 AND x is always 0, 1 OR x is always 1, but both 0 XOR x and 1 XOR x can be both 0 or 1 depending on x.
    – user7043
    Mar 30, 2014 at 13:49
  • 2
    @Netch There's only ambiguity if you talk about an n-ary extension of the XOR operation, but the standard definition is a binary (2-ary) operation, and I see nothing in the question or comments indicating that OP is asking about a n-ary extension.
    – user7043
    Mar 30, 2014 at 14:30
  • 2
    @Netch No, I didn't (well, except the paper introducing hamming codes). But 50's and 60's books wouldn't help your case, focus and terminology change. Again, these extensions and their ambiguity is real but the default meaning of "XOR" is the 2-ary operation. Unless the speaker says "n-ary XOR" or something to that effect, I will not assume those extensions are of interest. Doubly so in the context of operators in programming languages, which are virtually always unary and binary, with longer expression just being nested application of the binary operation.
    – user7043
    Mar 30, 2014 at 14:41

4 Answers 4

Reset to default
14

Binary

Nand

Lets look at how NAND can be implemented with just AND or OR gates.

NAND becomes one of:

!(a && b)
!a || !b

Either of these can be seen as short circuiting. The reason that NAND doesn't exist is that it is easily rewritten as not(a and b)

Xor

XOR, is at its heart, a parity checker. To check the parity of two values, you need to test both values. This is why it is fundamentally not able to short circuit it - you can't validate if the value is true or false until you test all the values.

Looking at how XOR is written with AND and OR gates:

(a || b) && !(a && b)

If a is true, the OR part of the xor can be short circuited, however it also means that the AND part cannot be short circuited.

N-ary

N-ary operands take any number of inputs (compared to the binary ones that just take two).

Nand

The n-ary NAND is

!(a && b && c && d ... )

This again can be short circuited in that as soon as one of operands evaluates to false, the value of the NAND is true.

Xor

There are two different interpretations of the n-ary xor:

  1. An odd number of true operand
  2. One and only one true operand

The first one is in common usage (see XOR at Wolfram):

For multiple arguments, XOR is defined to be true if an odd number of its arguments are true, and false otherwise. This definition is quite common in computer science, where XOR is usually thought of as addition modulo 2.

From Wikipedia

Strict reading of the definition of exclusive or, or observation of the IEC rectangular symbol, raises the question of correct behaviour with additional inputs. If a logic gate were to accept three or more inputs and produce a true output if exactly one of those inputs were true, then it would in effect be a one-hot detector (and indeed this is the case for only two inputs). However, it is rarely implemented this way in practice.

The 'one hot' xor may be short circuited when evaluating the expression when finding the second true value.

Otherwise, again, the XOR is more commonly implemented as the "odd number of true values" which serves as a parity checker and requires the evaluation of all the operands to determine the truth of the expression as the last value evaluated can always change the truth of the expression.

Improve this answer
13

NAND is either !a || !b or !(a && b) both will be short circuited when a is false.

XOR can't be short circuited at all as @delnan explained

Improve this answer
4

Perl6 has got short-circuit XOR but its meaning of XOR is specific. I've repeat my comment jist here: there are two meanings of XOR:

  1. if count of true arguments is odd
  2. if only exactly one argument is true

Example for difference: XOR (True, True, True) gives True with the 1st meaning and False with the 2nd meaning. If Perl6 machine detects at least 2 arguments are true, it stops evaluation of rest because result is already determined as False.

But, for the 1st meaning (more traditional), one can't determine final result until all arguments are evaluated.

I think we should invent special clarification terms for these XOR variants, even if they won't be used outside of this discussion.

Improve this answer
2
  • First one isn't XOR, it's parity function. They get conflated because for 2 inputs they are the same.
    – Ben Voigt
    Mar 30, 2014 at 21:23
  • @BenVoigt I agree with your terms but the issue is that you should convince the majority.
    – Netch
    Mar 31, 2014 at 6:34
2

The short answer is because the truth table for XOR doesn't have a single row of True's or False's.

  • If the first argument to OR is True, then the answer is True, regardless of the second argument.

  • If the first argument of AND is False, then the answer is False regardless of the second argument.

  • BUT If the first argument of XOR is True, or False, it still needs the second argument because the truth value may "flip":

True OR ? = True (always)

False AND ? = False (always)

True XOR ? = False or True

False XOR ? = True or False

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.