This discussion is archived
8 Replies Latest reply: Aug 24, 2007 6:04 AM by 807605 RSS

Behaviour of the boolean XOR ^ operator

807605 Newbie
Currently Being Moderated
Dear all

I have a simple enough requirement for a method to return true if one and only one of four supplied parameters are true. I would have predicted that the XOR operator ^ would make this a very straight forward task thus:
   /**
     * @return true if exactly one of the given parameters is true.
     */
    boolean xOrTest(boolean a, boolean b, boolean c, boolean d) {

        if (a ^ b ^ c ^ d) {
            return true;
        }
        return false;
    }
but this does not work in the following scenario (remember I want the method to return false because more than one parameter is true).
System.out.println(xOrTest(false, true, true, true));
infact returns true. My question is, can someone explain why ^ behaves this way and can ^ be used to efficiently meet the requirement?

Appendix:
The following scenarios all work as I would expect and print false:
System.out.println(xOrTest(false, false, true, true));
System.out.println(xOrTest(false, false, false, true));
System.out.println(xOrTest(false, false, false, false));
System.out.println(xOrTest(true, true, true, true));
The following scenarios all work as I would expect and print true:
System.out.println(xOrTest(true, false, false, false));
System.out.println(xOrTest(false, true, false, false));
System.out.println(xOrTest(false, false, true, false));
System.out.println(xOrTest(false, false, false, true));
regards

David
  • 1. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    ... infact returns true. My question is,
    can someone explain why ^ behaves this way and can ^
    be used to efficiently meet the requirement?
    It's supposed to work this way. The calculation goes like this:

    false ^ true equals true
    true ^ true equals false
    false ^ true equals true, the final result.

    So no, ^ won't provide an efficient implementation. Instead, I'd probably explicity count the trues:
    int count = 0;
    if (a) count++;
    if (b) count++;
    if (c) count++;
    if (d) count++;
    return count == 1;
  • 2. Re: Behaviour of the boolean XOR ^ operator
    JoachimSauer Journeyer
    Currently Being Moderated
    Do you want to know why this doesn't work? It should be somewhat obvious, when you read the description of Xor.

    I wouldn't care about efficiency in this kind of methods. Only optimize, when you find out that this method is indeed a bottleneck, otherwise just write a simple implementation (simple implementations are usually easier to optimize for the JIT compiler, than "clever" impelementations).

    primitive implementation:
    boolean xOrTest(boolean a, boolean b, boolean c, boolean d) {
      int trueCount = 0;
    
      if (a) {
        trueCount++;
      }
    
      if (b) {
        trueCount++;
      }
    
      if (c) {
        trueCount++;
      }
    
      if (d) {
        trueCount++;
      }
    
      return trueCount==1;
    }
  • 3. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    Apologies - there is an error in my appendix. There are three not four scenarios where the method correctly returns false:
    System.out.println(xOrTest(false, false, true, true));
    System.out.println(xOrTest(false, false, false, false));
    System.out.println(xOrTest(true, true, true, true));
  • 4. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    boolean xOrTest(boolean a, boolean b, boolean c,
    boolean d) {
    ...
    >
    About time to rename the method ... :-)
  • 5. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    About time to rename the method ... :-)
    Yes indeed! Thank you for your very speedy resposes

    David
  • 6. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    You have probably noticed that Joachims code is many more lines than mine even though we both use the same idea. Joachim is right in putting in the braces { and } since the Java coding conventions say you should. I rather deliberately break that rule when my if statement fits on one line. You decide whether you do the same.
  • 7. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    JoachimSauer wrote:
    I wouldn't care about efficiency in this kind of methods. Only optimize,
    when you find out that this method is indeed a bottleneck, otherwise just
    write a simple implementation (simple implementations are usually easier
    to optimize for the JIT compiler, than "clever" impelementations).
    I agree with you, and when you recommend to basically "write dumb code", this interview with Brian Goetz crosses my mind: http://java.sun.com/developer/technicalArticles/Interviews/goetz_qa.html
    But given that the prolem at hand is Boolean, why not make a simple straightforward approach:

    !((a & b) | (a & c) | (a & d) | (b & c) | (b & d) | (c & d)), which leads to
    !((a & (b | c | d)) | (b & (c | d)) | (c & d)) or
    boolean xor(final boolean a, final boolean b, final boolean c, final boolean d) {
      return !((a & (b | c | d)) || (b & (c | d)) || (c & d));
    }
    I consider this an acceptable solution, too.

    EDIT:
    No, not anymore! It may look nice and all, but is not quite XOR... so I apologize for being careless and not double-checking what I wrote (my "xor" returns true even if all arguments are false) -- sorry!

    This should (hopefully) be correct:
    EDIT2:
    <del>[...]</del>
    Aarrgh, but it's still horribly wrong! Made the same mistake twice, now I'll take some time to really think before totally embarrassing myself today...

    But I have to admit that JoachimSauer's solution is indeed simpler and is probably the right choice...

    Message was edited (2x) by:
    oebert: correction

    Message was edited by:
    oebert
  • 8. Re: Behaviour of the boolean XOR ^ operator
    807605 Newbie
    Currently Being Moderated
    Reply #7, cont.: Ok, just for the records (my original mistake was the wrong initial term for xor4):
    // (a & !(b | c | d)) | (b & !(a | c | d)) | (c & !(a | b | d)) | (d & !(a | b | c))
    // = (a & !b & !c & !d) | (b & !a & !c & !d) | (c & !a & !b & !d) | (d & !a & !b & !c)
    // = (((a & !b) | (!a & b)) & !c & !d) | (!a & !b &  ((c & !d) | (!c & d)))
    // = ((a ^ b) & !c & !d) | (!a & !b & (c ^ d))
    which can be coded like:
    boolean xor(final boolean a, final boolean b, final boolean c, final boolean d) {
      return ((a ^ b) && !c && !d) || (!a && !b && (c ^ d));
    }
    Umm, well... so much for the "simple straightforward approach"...
    Final assessment: overkill (now that it's there one could also use it, of course 8-)
    (Note to self: stay away from discussions about Boolean logic for a while...)