Personal computing discussed

Moderators: renee, SecretSquirrel, just brew it!

 
Crayon Shin Chan
Minister of Gerbil Affairs
Topic Author
Posts: 2313
Joined: Fri Sep 06, 2002 11:14 am
Location: Malaysia
Contact:

Quick XOR question

Wed Sep 21, 2011 2:59 pm

if(i==0 ^ j==0) //openlist[2][0] is the G cost
openlist[2][0].push_back(10);

In an implementation of the A* pathfinding algorithm, I want the second line to be executed whenever i is 0 or j is 0, but not when both are 0. That's an exclusive OR. Looks like there is no logic XOR, only a "bitwise XOR", whatever that means.

In any case Visual Studio 2003 gives a warning C4554, which seems to indicate that the XOR operator might not do what I want it to do. Should I worry about this? Or should I write another if condition between the 1st and 2nd lines?
Mothership: FX-8350, 12GB DDR3, M5A99X EVO, MSI GTX 1070 Sea Hawk, Crucial MX500 500GB
Supply ship: [email protected], 12GB DDR3, M4A88TD-V EVO/USB3
Corsair: Thinkpad X230
 
thegleek
Darth Gerbil
Posts: 7460
Joined: Tue Jun 10, 2003 11:06 am
Location: Detroit, MI
Contact:

Re: Quick XOR question

Wed Sep 21, 2011 3:12 pm

Crayon Shin Chan wrote:
I want the second line to be executed whenever i is 0 or j is 0, but not when both are 0. That's an exclusive OR.

Um.. Why can't you just use this?

if ((i==0 || j==0) && !(i==0 && j==0)) {
...true...
} else {
...false...
}
 
Crayon Shin Chan
Minister of Gerbil Affairs
Topic Author
Posts: 2313
Joined: Fri Sep 06, 2002 11:14 am
Location: Malaysia
Contact:

Re: Quick XOR question

Wed Sep 21, 2011 3:22 pm

Cool, thanks!
Mothership: FX-8350, 12GB DDR3, M5A99X EVO, MSI GTX 1070 Sea Hawk, Crucial MX500 500GB
Supply ship: [email protected], 12GB DDR3, M4A88TD-V EVO/USB3
Corsair: Thinkpad X230
 
cheesyking
Minister of Gerbil Affairs
Posts: 2756
Joined: Sun Jan 25, 2004 7:52 am
Location: That London (or so I'm told)
Contact:

Re: Quick XOR question

Wed Sep 21, 2011 3:37 pm

Crayon Shin Chan wrote:
Looks like there is no logic XOR, only a "bitwise XOR", whatever that means.


bitwise means you're comparing the binary representation of two numbers so XORing 1 with 2

1 01
2 10
3 11

so I assume you should do something like:

...
if(i ^ j)
...

EDIT:
I must admit I always do it gleeks way, doing a bitwise xor is probably faster but it's also probably not so easy to understand what it's doing when you come to look at the code again in months or even years time, especially if it's not something you do very often.
Fernando!
Your mother ate my dog!
 
thegleek
Darth Gerbil
Posts: 7460
Joined: Tue Jun 10, 2003 11:06 am
Location: Detroit, MI
Contact:

Re: Quick XOR question

Wed Sep 21, 2011 3:47 pm

cheesyking wrote:
I must admit I always do it gleeks way, doing a bitwise xor is probably faster but it's also probably not so easy to understand what it's doing when you come to look at the code again in months or even years time, especially if it's not something you do very often.

Good documentation goes a long way too... It's not YOURSELF that you have to worry about coming back to the code you wrote a year or more ago... What if you left the job and some poor schmuck straight out of college obtains your former job, starts to debug/trace through the code... Stops at the breakpoint where this XOR crap is... and goes WTFBBQ is this? And then proceeds to re-write it the way I posted it earlier... Just the ease of looking at it makes the world a better place!

Now... I can SEE if this is hard core embedded C or C++ where your code has to fit on a 4096k eeprom chip and you need to save as much character space as possible, then go with that crazy ^ XOR stuff, or better yet, scrap the C and learn some assembly! :P
 
dmjifn
Gerbil First Class
Posts: 103
Joined: Thu May 15, 2003 4:21 pm
Location: Indianapolis

Re: Quick XOR question

Wed Sep 21, 2011 4:19 pm

There is a logical XOR. The C# docs say:
Binary ^ operators are predefined for the integral types and bool. For integral types, ^ computes the bitwise exclusive-OR of its operands. For bool operands, ^ computes the logical exclusive-or of its operands; that is, the result is true if and only if exactly one of its operands is true.

What you are doing is syntactically correct given == has a higher precedence than ^. And, in fact, it works correct for me when I run it.
That warning advises you to use parens to clarify precedence, which is probably a good idea and may silence it.

Perhaps the existence of this thread proves the gleek's last point, but honestly I don't find logical XOR confusing.

Edit: After cruising through few more posts in the devden, it occurred to me you are probably talking about C++.
So the above isn't useful to you. :) Sorry! I will tell you if I truly needed logical xor often, I would probably write a fn or operator.
But for a one-off, I'd also just do the gleek's version and move on.
 
just brew it!
Administrator
Posts: 54500
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Quick XOR question

Wed Sep 21, 2011 4:45 pm

What do you want it to do in the case where both are *not* zero? You didn't specify in the original post.

XOR can also be viewed as a test for inequality; so you could achieve the same effect as a logical XOR with:
if ((i == 0) != (j == 0)) {
  // exactly one of i or j is zero
} else {
  // they are either both zero, or both non-zero
}
Nostalgia isn't what it used to be.
 
cheesyking
Minister of Gerbil Affairs
Posts: 2756
Joined: Sun Jan 25, 2004 7:52 am
Location: That London (or so I'm told)
Contact:

Re: Quick XOR question

Wed Sep 21, 2011 6:27 pm

if (i*j == 0) && (i+j != 0)
 


don't do this, I'm just being silly.
Fernando!

Your mother ate my dog!
 
SecretSquirrel
Minister of Gerbil Affairs
Posts: 2726
Joined: Tue Jan 01, 2002 7:00 pm
Location: North DFW suburb...
Contact:

Re: Quick XOR question

Thu Sep 22, 2011 7:39 am

Supposing that the most efficient way to represent the logical construct, in terms of program execution, is by an XOR, any decent compiler is going to identify all those patterns as being representation of an XOR and use that operation anyway.

When working with booleans, XOR is simply a non-equality operation. So (a != b) == (a^b) when a={0,1} and b={0,1}. However, if either is not a boolean then only bitwise XOR make sense. Given that, ((a==0) != (b==0)) is probably to "correct" test for a is zero or b is zero but a and b are not zero in C and C++, given the conditions you have.

If you have one of the two values that is more likely to not be zero at any given time (i, for example) then if(i==0 && i!=j) will produce slightly faster execution since if i==1, the first test is failed and the second inequality computation is short circuited.

In the end, there isn't a right way to do it. Personally I would probably either use ((i==0) ^ (j==0)) or ((i==0) != (j==0)). But then I have this expectation, probably unrealistic, that anyone programming a computer should have a basic understanding of boolean and bitwise logical operations and how they are represented in the language they are using.

--SS
 
TurtlePerson2
Graphmaster Gerbil
Posts: 1171
Joined: Sat May 26, 2007 9:08 am
Location: Dallas, Texas

Re: Quick XOR question

Thu Sep 22, 2011 9:07 am

SecretSquirrel wrote:
Supposing that the most efficient way to represent the logical construct, in terms of program execution, is by an XOR, any decent compiler is going to identify all those patterns as being representation of an XOR and use that operation anyway.


Exactly. A good compiler is supposed to do more than just turn your C++ code into machine instructions. It also optimizes the code, assigns registers, etc. All ALUs that I have studied have XOR as one of their functions, so it follows that most ISAs must therefore include an XOR instruction. The compiler is going to turn any XOR in your code into an XOR instruction, regardless of how you choose to implement it in your code.
"TORTURIS EXUVIAS EUNT"
Phenom X6 1090T @ 3.2 GHz
XFX Radeon RX 580
 
just brew it!
Administrator
Posts: 54500
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Quick XOR question

Thu Sep 22, 2011 9:32 am

TurtlePerson2 wrote:
... so it follows that most ISAs must therefore include an XOR instruction.

I would take that one step further and say that *all* sane ISAs must have an XOR instruction. It is a rather fundamental (and essential) construct at the assembly/machine language level.

Trivia: In many ISAs, XORing a register with itself is a useful shorthand for clearing that register. This may even execute faster (and take up less code space) than explicitly loading the value 0 (since the constant does not need to be stored in code memory and subsequently fetched to clear the register).
Nostalgia isn't what it used to be.
 
morphine
TR Staff
Posts: 11600
Joined: Fri Dec 27, 2002 8:51 pm
Location: Portugal (that's next to Spain)

Re: Quick XOR question

Thu Sep 22, 2011 9:41 am

just brew it! wrote:
Trivia: In many ISAs, XORing a register with itself is a useful shorthand for clearing that register. This may even execute faster (and take up less code space) than explicitly loading the value 0 (since the constant does not need to be stored in code memory and subsequently fetched to clear the register).

Been there, done that, in my assembly days.
There is a fixed amount of intelligence on the planet, and the population keeps growing :(
 
notfred
Maximum Gerbil
Posts: 4610
Joined: Tue Aug 10, 2004 10:10 am
Location: Ottawa, Canada

Re: Quick XOR question

Thu Sep 22, 2011 12:28 pm

morphine wrote:
just brew it! wrote:
Trivia: In many ISAs, XORing a register with itself is a useful shorthand for clearing that register. This may even execute faster (and take up less code space) than explicitly loading the value 0 (since the constant does not need to be stored in code memory and subsequently fetched to clear the register).

Been there, done that, in my assembly days.
And spent a couple of minutes staring at disassembled code going "WTF is the compiler doing that for?" before realising it was me that was the dunce...

Who is online

Users browsing this forum: No registered users and 1 guest
GZIP: On