Logical XOR operator in C++?
Asked Answered
U

12

386

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.

Ume answered 20/10, 2009 at 19:1 Comment(8)
Actually, Jim, that's not the only difference between & and && for example... 1 && 2 is True. but 1 & 2 => 0. Because of that, I think that "short circuiting" is just a property that they happen to have. Logical is the more important feature...Nor
Not to mention that 2 && 3 == true, but 2 & 3 == 2.Labyrinth
David Thomley: Well, yeah, but 2 ==> true, so that's ok... Remember, there really aren't any booleans...Nor
@BrianPostow: Actually, in C++, there are.Parfleche
As posted below, here's Dennis Ritchie's answer as to why it doesn't exist: c-faq.com/misc/xor.dmr.htmlSurrogate
Whats wrong using the ^ bitwise operator? For example a = 2, b = 5, c = 5 and (a == b ^ a ==c) will give the expected result.Wellnigh
Interesting that ^ works fine bools with g++/clang++/VSC++, but @greg-hewgill's answer is the most correct approach for logical xor (I said out load "duh" the instant I saw his answer).Anglaangle
I think a ^^ operator would be useful. The other solutions proposed below are rather kludgy.Sarracenia
I
699

The != operator serves this purpose for bool values.

Impregnate answered 20/10, 2009 at 19:3 Comment(13)
If both are false, doesn't the XOR should return false??? In this case, the != would return true.Ragwort
But false != false => falseCoxalgia
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 ^...Nor
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.Impregnate
If you want to do it for type a just write !(a) != !(a)Syllabize
@ChrisLutz: yes, but beware of overloaded operators.Dingo
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.)Gossett
Likewise, == functions as XNOR for a pair of booleans.Voncile
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.Gales
So, A==B==C means (A==B) XNOR C.Ilo
@Jonas, 0 XOR 0 => 0, so false != false => false is the expected result. XOR could also be called "either or (but not both)" false OR false is false, so false XOR false is also false.Kaiulani
@Kaiulani I believe Jonas was addressing David Brunelle's objection, not issuing a complaint.Naturalistic
@MarkReed Yes, I was confused about that as well. You are right.Spur
M
325

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.

Marquez answered 20/10, 2009 at 20:4 Comment(11)
I don't understand why A and B are negated with !Olid
Mainly to convert them to boolean. !! would work just ask well, but since they need to be different, negating them does no harm.Marquez
Question is, are compilers be able to properly optimize this.Galengalena
@Galengalena 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.Appear
@Aidiakapi: Not necessarily. If the eventual operation is boolean, a compiler might well try to minimize or canonicalize the formula.Galengalena
Not knowing the importance of normalizing bools costed me 2 days.Olaolaf
It is not easy to use it for odd number of args: 0^0^0==0, !0!=!0!=!0==1.Wil
@LiraNuna, "why A and B are negated with !" / "Mainly to convert them to boolean." - I think this is worth mentioning in the answer.Voncile
What does _Bool have to do with C++?Ottava
@Ottava 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.Geffner
why not simply if (bool(A) != bool(B)) ? imo, no need for negation.Gleiwitz
C
54

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.

Cleptomania answered 20/10, 2009 at 19:16 Comment(10)
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).Penmanship
@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.Cleptomania
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.Democritus
@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)Invective
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.Blamed
@hkBst: I think this is fully covered in the second part of my answer.Cleptomania
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.Annalist
@AnTstandswithRussia What is a sequence point?Hollandia
@MTV: Here is the Wikipedia article on sequence points.Annalist
It would need to be (a) ? !(b) : !!(b). Otherwise the result type would not necessarily be bool.Thedrick
S
25

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;
}
Stacee answered 7/10, 2012 at 12:17 Comment(3)
This approach can generate some quite slow code - 3-5x slower than (!a) != (!b) on both clang and gcc using libstdc++: quick-bench.com/xtv2StFkR8PCkV4fOiqSgeG1T4QOncoming
@Oncoming 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/umQRhhr0ZVS2o03fhCQAfN3HLakDelanadelancey
@Delanadelancey must have forgotten to remove the auto-generated benchmark it starts with. Sorry.Oncoming
F
17

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.

Forcier answered 20/10, 2009 at 19:2 Comment(35)
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.Rancorous
Ah, I never realized that picking & vs && was about short circuit eval - I thought it was just a code-clarity consideration. Thanks.Ume
@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.Forcier
-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.Nor
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.Milone
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.Nor
@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 &.Cleptomania
@Brian Postow: What would be the reason to introduce a && without short-circuiting?Cleptomania
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".Nor
@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 ^^Milone
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!Nor
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.Nor
@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.Cleptomania
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 +=?Nor
@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.Milone
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. :)Milone
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.Nor
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-)Nor
@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.Forcier
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...Nor
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...Nor
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.htmlMilone
@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.Forcier
@Brian: C99 is 10 years old now. It does have a bool type.Forcier
Mehrdad: On my computer, in gcc 4.2 bool does not compile. g++ it does.Nor
@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.Cleptomania
@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.Nor
@Brian Postow: In C99 the type is called Bool_. And there's a macro bool defined in stdbool.h.Cleptomania
@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)Nor
@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.Cleptomania
@AndreyT: It's 'Bool' not 'Bool'. It's surprising to me that C and C++ would have different names... odd.Nor
Sorry, its _Bool, not Bool_.Cleptomania
Here's a working link on Dennis Ritchie's answer as to why it doesn't exist: c-faq.com/misc/xor.dmr.htmlSurrogate
And the account of Dennis Ritchie of how and why the && and || where introduced in the first place (instead of using & and |).Logger
If someone think that Boolean operations can be performed between only Boolean variable, you are right.Pacificism
A
13

There was some good code posted that solved the problem better than !a != !b

Note that I had to add the BOOL_DETAIL_OPEN/CLOSE so it would work on MSVC 2010

/* From: http://groups.google.com/group/comp.std.c++/msg/2ff60fa87e8b6aeb

   Proposed code    left-to-right?  sequence point?  bool args?  bool result?  ICE result?  Singular 'b'?
   --------------   --------------  ---------------  ---------- ------------  -----------  -------------
   a ^ b                  no              no             no          no           yes          yes
   a != b                 no              no             no          no           yes          yes
   (!a)!=(!b)             no              no             no          no           yes          yes
   my_xor_func(a,b)       no              no             yes         yes          no           yes
   a ? !b : b             yes             yes            no          no           yes          no
   a ? !b : !!b           yes             yes            no          no           yes          no
   [* see below]          yes             yes            yes         yes          yes          no
   (( a bool_xor b ))     yes             yes            yes         yes          yes          yes

   [* = a ? !static_cast<bool>(b) : static_cast<bool>(b)]

   But what is this funny "(( a bool_xor b ))"? Well, you can create some
   macros that allow you such a strange syntax. Note that the
   double-brackets are part of the syntax and cannot be removed! The set of
   three macros (plus two internal helper macros) also provides bool_and
   and bool_or. That given, what is it good for? We have && and || already,
   why do we need such a stupid syntax? Well, && and || can't guarantee
   that the arguments are converted to bool and that you get a bool result.
     Think "operator overloads". Here's how the macros look like:

   Note: BOOL_DETAIL_OPEN/CLOSE added to make it work on MSVC 2010
  */

#define BOOL_DETAIL_AND_HELPER(x) static_cast<bool>(x):false
#define BOOL_DETAIL_XOR_HELPER(x) !static_cast<bool>(x):static_cast<bool>(x)

#define BOOL_DETAIL_OPEN (
#define BOOL_DETAIL_CLOSE )

#define bool_and BOOL_DETAIL_CLOSE ? BOOL_DETAIL_AND_HELPER BOOL_DETAIL_OPEN
#define bool_or BOOL_DETAIL_CLOSE ? true:static_cast<bool> BOOL_DETAIL_OPEN
#define bool_xor BOOL_DETAIL_CLOSE ? BOOL_DETAIL_XOR_HELPER BOOL_DETAIL_OPEN
Arly answered 6/9, 2012 at 2:46 Comment(0)
G
10

(A || B) && !(A && B)

The first part is A OR B, which is the Inclusive OR; the second part is, NOT A AND B. Together you get A or B, but not both A and B.

This will provide the XOR proved in the truth table below.

|-----|-----|-----------|
|  A  |  B  |  A XOR B  |
|-----|-----|-----------|
|  T  |  T  |   False   |
|-----|-----|-----------|
|  T  |  F  |   True    |
|-----|-----|-----------|
|  F  |  T  |   True    |
|-----|-----|-----------|
|  F  |  F  |   False   |
|-----|-----|-----------|
Glycoside answered 28/1, 2018 at 0:58 Comment(3)
I'm not digging the performance on this approach: quick-bench.com/PgNgGN8ATrKt7el1dAaJj7QtuF4Oncoming
There's no need to be defensive about it.Oncoming
@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?Joint
I
6

Use a simple:

return ((op1 ? 1 : 0) ^ (op2 ? 1 : 0));
Ivy answered 29/7, 2015 at 8:33 Comment(0)
B
6

Here is how I think you write an XOR comparison in C++:

bool a = true;   // Test by changing to true or false
bool b = false;  // Test by changing to true or false
if (a == !b)     // THIS IS YOUR XOR comparison
{
    // do whatever
}

Proof

XOR TABLE
 a   b  XOR
--- --- ---
 T   T   F
 T   F   T
 F   T   T
 F   F   F

a == !b TABLE
 a   b  !b  a == !b
--- --- --- -------
 T   T   F     F
 T   F   T     T
 F   T   F     T
 F   F   T     F

The proof is that an exhaustive study of inputs and outputs shows that in the two tables, for every input set the result is always the identical in the two tables.

Therefore, the original question being how to write:

return (A==5) ^^ (B==5)

The answer would be

return (A==5) == !(B==5);

Or if you like, write

return !(A==5) == (B==5);
Bills answered 13/9, 2016 at 15:0 Comment(1)
!a != !b seems to be nicer because it converts your arguments to bool for you.Oncoming
B
0

I use "xor" (it seems it's a keyword; in Code::Blocks at least it gets bold) just as you can use "and" instead of && and "or" instead of ||.

if (first xor second)...

Yes, it is bitwise. Sorry.

Biernat answered 20/10, 2009 at 19:36 Comment(9)
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)Nor
@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).Cleptomania
@Brian Postow: ... xor stands for bitwise xor though, while and is logical and.Cleptomania
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-)Nor
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...Nor
@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.Syllabize
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.Milone
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 .Milone
why wouldn't you delete your "answer" once you realized it wasn't an answer?Oncoming
S
0
return ((A==5) != (B==5))


+------+------+--------+-----+
| A==5 | B==5 | op(==) | !op |
+------+------+--------+-----+
|    0 |    0 |      1 |   0 |
|    0 |    1 |      0 |   1 |
|    1 |    0 |      0 |   1 |
|    1 |    1 |      1 |   0 |
+------+------+--------+-----+
Swec answered 28/9, 2023 at 3:50 Comment(0)
Q
-1
#if defined(__OBJC__)
    #define __bool BOOL
    #include <stdbool.h>
    #define __bool bool
#endif

static inline __bool xor(__bool a, __bool b)
{
    return (!a && b) || (a && !b);
}

It works as defined. The conditionals are to detect if you are using Objective-C, which is asking for BOOL instead of bool (the length is different!)

Quinze answered 18/5, 2013 at 10:49 Comment(4)
This violates the double underscore rule.Sclerometer
@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.Quinze
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.Sclerometer
@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.Quinze

© 2022 - 2024 — McMap. All rights reserved.