Logical XOR operator in C++?

Question

Is there such a thing? It is the first time I encountered a practical need for it, but I don't see one listed in Stroustrup. I intend to write:

// Detect when exactly one of A,B is equal to five.
return (A==5) ^^ (B==5);

But there is no ^^ operator. Can I use the bitwise ^ here and get the right answer (regardless of machine representation of true and false)? I never mix & and &&, or | and ||, so I hesitate to do that with ^ and ^^.

I'd be more comfortable writing my own bool XOR(bool,bool) function instead.

Solution 1

The != operator serves this purpose for bool values.

Solution 2

For a true logical XOR operation, this will work:

if(!A != !B) {
    // code here
}

Note the ! are there to convert the values to booleans and negate them, so that two unequal positive integers (each a true) would evaluate to false.

Solution 3

Proper manual logical XOR implementation depends on how closely you want to mimic the general behavior of other logical operators (|| and &&) with your XOR. There are two important things about these operators: 1) they guarantee short-circuit evaluation, 2) they introduce a sequence point, 3) they evaluate their operands only once.

XOR evaluation, as you understand, cannot be short-circuited since the result always depends on both operands. So 1 is out of question. But what about 2? If you don't care about 2, then with normalized (i.e. bool) values operator != does the job of XOR in terms of the result. And the operands can be easily normalized with unary !, if necessary. Thus !A != !B implements the proper XOR in that regard.

But if you care about the extra sequence point though, neither != nor bitwise ^ is the proper way to implement XOR. One possible way to do XOR(a, b) correctly might look as follows

a ? !b : b

This is actually as close as you can get to making a homemade XOR "similar" to || and &&. This will only work, of course, if you implement your XOR as a macro. A function won't do, since the sequencing will not apply to function's arguments.

Someone might say though, that the only reason of having a sequence point at each && and || is to support the short-circuited evaluation, and thus XOR does not need one. This makes sense, actually. Yet, it is worth considering having a XOR with a sequence point in the middle. For example, the following expression

++x > 1 && x < 5

has defined behavior and specificed result in C/C++ (with regard to sequencing at least). So, one might reasonably expect the same from user-defined logical XOR, as in

XOR(++x > 1, x < 5)

while a !=-based XOR doesn't have this property.

Solution 4

There is another way to do XOR:

bool XOR(bool a, bool b)
{
    return (a + b) % 2;
}

Which obviously can be demonstrated to work via:

#include <iostream>

bool XOR(bool a, bool b)
{
    return (a + b) % 2;
}

int main()
{
    using namespace std;
    cout << "XOR(true, true):\t" << XOR(true, true) << endl
         << "XOR(true, false):\t" << XOR(true, false) << endl
         << "XOR(false, true):\t" << XOR(false, true) << endl
         << "XOR(false, false):\t" << XOR(false, false) << endl
         << "XOR(0, 0):\t\t" << XOR(0, 0) << endl
         << "XOR(1, 0):\t\t" << XOR(1, 0) << endl
         << "XOR(5, 0):\t\t" << XOR(5, 0) << endl
         << "XOR(20, 0):\t\t" << XOR(20, 0) << endl
         << "XOR(6, 6):\t\t" << XOR(5, 5) << endl
         << "XOR(5, 6):\t\t" << XOR(5, 6) << endl
         << "XOR(1, 1):\t\t" << XOR(1, 1) << endl;
    return 0;
}

Solution 5

The XOR operator cannot be short circuited; i.e. you cannot predict the result of an XOR expression just by evaluating its left hand operand. Thus, there's no reason to provide a ^^ version.

View more solutions

Comments

[Martin Beckett]

Just to clarify, that means to check for XOR you have to evaluate both parts of the test. So there is no advantage to having a symbol. C/C++ is allowed to skip unecessary parts of a comparison if the over result is known after the first test.

[RAC]

Ah, I never realized that picking & vs && was about short circuit eval - I thought it was just a code-clarity consideration. Thanks.

[mmx]

@RAC: Actually, it's an important thing to know. That's why things like if (x != NULL && x->IsValid()) work correctly. With &, it would try to evaluate x->IsValid() even if the x pointer is null.

[Brian Postow]

-1 because the main difference between && and & is not just the short circuiting. 1 && 2 is True, but 1 & 2 is false. Short circuiting is just a handy side effect.

[David Brunelle]

If both are false, doesn't the XOR should return false??? In this case, the != would return true.

[Johannes Schaub - litb]

The answer is not talking about && and & at all. Its point is that there is no reason to introduce ^^. The property that ^^ would regard any non-null value as 1 is not really useful, i suspect. Or at least i can't see any use.

[Jonas]

But false != false => false

[Brian Postow]

The reason that there's no reason to introduce ^^ has nothing to do with short circuiting. It's that != works perfectly well, as Greg mentioned. There WOULD be a reason to introduce && even if short circuiting was not an issue.

[AnT stands with Russia]

@Brian Postow: What Mehrdad says is about the difference between logical XOR and && (or ||). He didn't say anything at all about the difference between && and &.

[AnT stands with Russia]

@Brian Postow: What would be the reason to introduce a && without short-circuiting?

[Brian Postow]

I'm guessing that those are hidden #defines from somewhere. I'm pretty sure "and" and "xor" aren't keywords in ansi C... ( at least not C79)

[Brian Postow]

Andry: you need && to get logical "and" & doesn't cut it because it's bit wise. 1 & 2 ==> 0. whereas you want it to be "true".

[Johannes Schaub - litb]

@Brain, yes the reason that the answer doesn't handle converting to true or false from non-zero and zero is that != already does this, i think (only mehrdad can know for sure, of course). So the only property ^^ would have left is short curciut (which != doesn't have). But as this answer also points out, this is nonsensical for ^^

[Brian Postow]

Andrey: (sorry for misspelling your name 1st time) the reason I'm bringing up && s & is that Mehrdad is saying that the sole reason to have a XOR operator would be to have short circuit. However short circuit is a complete red herring. && and || are LOGICAL operators that operate on the entire number, whereas & and | and ^ are bitwise that operate on the bits. they behave completely differently, even in languages (there are some) that don't do short circuiting!

[AnT stands with Russia]

@Brian Postow: I don't know what C79 is, but in C++98 and and xor are standard library macros. Thay are not from "somewhere", they are from <iso646.h>. These macros are also in C99 (not sure about C89/90).

[Brian Postow]

litb: Converting to true and false isn't really the issue. The issue is that logical operators behave differently than bitwise operators when given values that are neither 1 nor 0.

[AnT stands with Russia]

@Brian Postow: ... xor stands for bitwise xor though, while and is logical and.

[Brian Postow]

I mistyped C89 as C79... and and xor etc are not in my copy of K&R. I don't think I've ever used iso686.h, at least not knowingly... and so, yes, they are #defines from somewhere, you just happen to know where that somewhere is B-)

[AnT stands with Russia]

@Brian Postow: No, if these operators were introduced just to have them as "logical" operators, we'd undoubtedly see logical XOR introduced as well (why not?). Or we wouldn't see any logical operators at all (use &, | and ^ with manual normalization). The fact that we have && and || and nothing else clearly means that the main reason to introduce these was short-circuit evaluation.

[Brian Postow]

and Andrey, you are correct. xor does not do logical xor, as 1 xor 2 => 3 which is true, and you want it to be false...

[Brian Postow]

AndreyT: no, we don't need xor because 1) it can be constructed via && and || and !. 2) it can be done via !=. There are languages with logical && (or equivalent) that do NOT SHORT CIRCUIT. Also, are you saying that C wouldn't give us && because we could create it with & and (x !=0)? if C never gave us unnecessary short cuts, why would we have ++ or +=?

[Johannes Schaub - litb]

@Brian the point is that if you give ^^ a "logical" mood without short-circuit, then ^^ is not any different to !=. This answer hilights a difference to != that ^^ would have, but which would not make sense.

[Johannes Schaub - litb]

Also C++ != other-languages. In C and C++ as shown above short circuit is not just some-nice-to-have-stuff but it's fundamentally important. :)

[Brian Postow]

litb: That's true. However, I think that the important part of that explanation is that you can use !=, not that it doesn't allow short circuiting.

[Brian Postow]

litb: It's actually NOT fundamentally important. You can always split it into multiple if... it's just a convenience like ++. Fundamentally, though I think we're getting into a discussion of language design here. I think we all understand and agree on what is "true". We disagree on what is "important" and that skirts into opinion territory. B-)

[Brian Postow]

Note that this only works for booleans. And ^ would work perfectly well there. 2 !=1 => 1 which is not what you want! as LiraNuna says, putting a ! infront of both sides solves that problem. but again, then you can use bitwise ^...

[mmx]

@Brian: "you need && to get logical "and" & doesn't cut it because it's bit wise." Not true. The compiler can use the static type information of the operands to choose between "logical" and "bitwise" versions with a single operator. Strictly speaking, you don't need to have two distinct operators. Look at C#: for bool operands, the sole difference between & and '&&` is short circuiting.

[Brian Postow]

Also, the more I think about this, the more I think that C SHOULD have a ^^ operator, that would avoid having to negate both sides (or some other normalization to 1/0) before doing !=... I'm guessing it's not because xor isn't used nearly as often... but your mileage may vary...

[Brian Postow]

Mehrdad: C and C++ don't have true Boolean types. they have ints that pretend to be booleans. IF you had operator overloading and booleans then you wouldn't need && ever. You could just have the boolean & do short circuiting and the number & not...

[Johannes Schaub - litb]

Then you should read Dennis Ritchie's answer to why it doesn't exist: it.usyd.edu.au/~dasymond/mirror/c-faq/misc/xor.dmr.html

[mmx]

@Brian: My comment applies to typed languages in general and AFAIK, both C and C++ in their current versions have bool types. The difference is that C, C++ support coercions from ints to bools.

[mmx]

@Brian: C99 is 10 years old now. It does have a bool type.

[Brian Postow]

Mehrdad: On my computer, in gcc 4.2 bool does not compile. g++ it does.

[AnT stands with Russia]

@Brian Postow: I don't know where you get that strange info about bool type. C89/90 didn't have a real boolean type, but bool in C++ and Bool_ in C99 are true dedicated boolean types.

[Brian Postow]

@litb: I stand corrected. If Dennis Ritchie says it, it must be true. I still think it would be a useful short-cut like ++, but I bow to the experience of Ritchie.

[AnT stands with Russia]

@Brian Postow: In C99 the type is called Bool_. And there's a macro bool defined in stdbool.h.

[Brian Postow]

@AndreyT: Brians-mini$ gcc-4.2 foo.c foo.c: In function 'main': foo.c:5: error: 'Bool_' undeclared (first use in this function) ... foo.c:6: error: 'bool' undeclared (first use in this function)

[AnT stands with Russia]

@Brian Postow: The key moment being that it exists in C99 only. You need to compile with -std=c99 switch. to make gcc work in C99 mode. It is nor default still.

[Brian Postow]

@AndreyT: It's 'Bool' not 'Bool'. It's surprising to me that C and C++ would have different names... odd.

[AnT stands with Russia]

Sorry, its _Bool, not Bool_.

[Greg Hewgill]

Right, I was careful to mention "for bool values" because it doesn't necessarily do what you might want for non-booleans. And as this is C++, there exists a real bool type instead of having to use int for that purpose.

[visual_learner]

If you want to do it for type a just write !(a) != !(a)

[visual_learner]

@Andrey - I've never seen anything about these macros in C99. They're easy to implement, and I bet many implementations will provide them, but please cite where the standard mandates them.

[Johannes Schaub - litb]

They are certainly in C99 using that header. In C++, they are integrated into the language as "alternative tokens", and you can do struct A { compl A() { } }; to define a destructor, for example.

[Johannes Schaub - litb]

i believe it's not part of C89, but it's part of the normative addendum that was released as C94: lysator.liu.se/c/na1.html .

[Exectron]

You're missing the other important thing about || and &&: C) they evaluate the operands in a boolean context. That is, 1 && 2 is true, unlike 1 & 2 which is zero. Likewise, a ^^ operator could be useful for providing this extra feature, of evaluating the operands in a boolean context. E.g. 1 ^^ 2 is false (unlike 1 ^ 2).

[AnT stands with Russia]

@Craig McQueen: I'm not missing it. The second paragraph of my post mentions it. In my opinion, treating operands as boolean values is not a critical feature of logical operators, in a sense that they would not be introduced for that reason alone. The main reason they were introduced is short-circuited evaluation and the sequence point required for that.

[Martin Hansen]

I don't understand why A and B are negated with !

[LiraNuna]

Mainly to convert them to boolean. !! would work just ask well, but since they need to be different, negating them does no harm.

[einpoklum]

Question is, are compilers be able to properly optimize this.

[Tobia]

Here's a working link on Dennis Ritchie's answer as to why it doesn't exist: c-faq.com/misc/xor.dmr.html

[Aidiakapi]

@einpoklum Pure speculation, but I'd bet on no. Even if the compiled could ensure that the bool values are indeed a 0 or 1 (or whatever the system uses), which should be possible because of the first '!', they'd still have to have a specific optimization for an (in)equality between two of those boolean values. Seems too much trouble for an arguably insignificant and easily manually code able optimization.

[einpoklum]

@Aidiakapi: Not necessarily. If the eventual operation is boolean, a compiler might well try to minimize or canonicalize the formula.

[Tamás Szelei]

This violates the double underscore rule.

[Maxthon Chan]

@TamásSzelei Not necessarily as the compiler does not see that as it si preprocessed away, and in Objective-C world double underscores are fairly common.

[Tamás Szelei]

Good point about the preprocessor, although to me it's still code smell this way (why use a macro instead a typedef anyway?). Also, the question was not about Objective-C.

[Maxthon Chan]

@TamásSzelei Well I used to have a habit of sharing header files around across multiple languages, and usually all headers come from Objective-C. My new code don't smell too much now, but the double underscore are still used from time to time to adhere with ObjC habits.

[rwong]

@ChrisLutz: yes, but beware of overloaded operators.

[0 _]

And the account of Dennis Ritchie of how and why the && and || where introduced in the first place (instead of using & and |).

[Makan Tayebi]

Not knowing the importance of normalizing bools costed me 2 days.

[RAs]

Nowadays, would your suggestion still only work with a macro? Although it's true that order of parameters to be evaluated in a function is compiler-dependent, isn't it currently rare to differ from left-to-right? Also, it might worth to note here in the comments that if an implementation looks like #define XOR(ll,rr) { ll ? !rr : rr }, then a call like int x = 2; XOR(++x > 1, x < 5); will give the wrong result. The call would have to have extra parentheses, like in int x = 2; XOR( (++x > 1), (x < 5) );, in order to give the correct expected result.

[grek40]

@user2019840 when actually implementing a preprocessor macro, you always have to be extra-careful with parenthesis. Don't leave this aspect to the caller. So it might be something like #define XOR(a, b) (a) ? !(b) : (b)

[Euri Pinhollow]

It is not easy to use it for odd number of args: 0^0^0==0, !0!=!0!=!0==1.

[hkBst]

Since XOR cannot short-circuit, there is no need for a sequence-point. XOR is more like + in that regard. Unless you also want to argue for (++x) + x being equal to 2x+1, the sequence point is not reasonable.

[AnT stands with Russia]

@hkBst: I think this is fully covered in the second part of my answer.

[Tiefan Ju]

If someone think that Boolean operations can be performed between only Boolean variable, you are right.

[Rico Picone]

For those finding this while looking for xor in C: this works properly for ints, too. The case to check, of course, is 0!=0, which returns 0, as it should for xor. (Tested on gcc.)

[cp.engr]

@LiraNuna, "why A and B are negated with !" / "Mainly to convert them to boolean." - I think this is worth mentioning in the answer.

[cp.engr]

Likewise, == functions as XNOR for a pair of booleans.

[xaxxon]

This approach can generate some quite slow code - 3-5x slower than (!a) != (!b) on both clang and gcc using libstdc++: quick-bench.com/xtv2StFkR8PCkV4fOiqSgeG1T4Q

[xaxxon]

I'm not digging the performance on this approach: quick-bench.com/PgNgGN8ATrKt7el1dAaJj7QtuF4

[xaxxon]

!a != !b seems to be nicer because it converts your arguments to bool for you.

[xaxxon]

why wouldn't you delete your "answer" once you realized it wasn't an answer?

[xaxxon]

There's no need to be defensive about it.

[Ruslan]

What does _Bool have to do with C++?

[SoLaR]

@xaxxon: Don't see the point in this benchmarks!? In StringCreation you used in creation of string, but in second benchmark you didn't. If you place identical code in both benchmarks, and call different XOR's for each benchmark (XOR, and XOR2) you get same benchmark results. So what have you been trying to say?

[Michael Choi]

@Ruslan I was going to say the same thing. I'd assume maybe a typedef from _Bool to bool? Anyways, I realize how old this thread is but I think (bool) x is much more readable and explicit than !!x.

[Admin]

consider following as well as XOR solution if (*s1 == '\0' != *s2 == '\0') where s1 and s2 are strings of course. This does not return same output as XOR.

[gmargari]

@xaxxon your benchmark is not correct: one of the two functions benchmarked creates a (unrelated) string inside its loop. Removing this, the code is only 30% slower. quick-bench.com/q/umQRhhr0ZVS2o03fhCQAfN3HLak

[xaxxon]

@gmargari must have forgotten to remove the auto-generated benchmark it starts with. Sorry.

[Darko Veberic]

why not simply if (bool(A) != bool(B)) ? imo, no need for negation.

[Andreas Wenzel]

It would be better to write a ? !b : !!b instead of a ? !b : b, because otherwise, the expression could return a value that is neither 0 nor 1. All logical operators evaluate to either 0 or 1, so it would be better if the solution behaved the same way.

[QuentinUK]

So, A==B==C means (A==B) XNOR C.