Quick XOR question

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Quick XOR question

Postposted on Wed Sep 21, 2011 2:59 pm

Code: Select all
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: Thuban 1055T@3.7GHz, 12GB DDR3, M5A99X EVO, GTX470+Icy Vision Rev.2@840/3800, Vertex 2E 60GB
Supply ship: Sargas@2.8GHz, 12GB DDR3, M4A88TD-V EVO/USB3
Corsair: Macbook Air Ivy Bridge
Crayon Shin Chan
Minister of Gerbil Affairs
 
Posts: 2238
Joined: Fri Sep 06, 2002 11:14 am
Location: Malaysia

Re: Quick XOR question

Postposted on 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...
}
thegleek
Darth Gerbil
Gold subscriber
 
 
Posts: 7360
Joined: Tue Jun 10, 2003 11:06 am
Location: Detroit, MI

Re: Quick XOR question

Postposted on Wed Sep 21, 2011 3:22 pm

Cool, thanks!
Mothership: Thuban 1055T@3.7GHz, 12GB DDR3, M5A99X EVO, GTX470+Icy Vision Rev.2@840/3800, Vertex 2E 60GB
Supply ship: Sargas@2.8GHz, 12GB DDR3, M4A88TD-V EVO/USB3
Corsair: Macbook Air Ivy Bridge
Crayon Shin Chan
Minister of Gerbil Affairs
 
Posts: 2238
Joined: Fri Sep 06, 2002 11:14 am
Location: Malaysia

Re: Quick XOR question

Postposted on 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!
cheesyking
Minister of Gerbil Affairs
 
Posts: 2253
Joined: Sun Jan 25, 2004 7:52 am
Location: That London (or so I'm told)

Re: Quick XOR question

Postposted on 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
thegleek
Darth Gerbil
Gold subscriber
 
 
Posts: 7360
Joined: Tue Jun 10, 2003 11:06 am
Location: Detroit, MI

Re: Quick XOR question

Postposted on 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.
dmjifn
Gerbil
Gold subscriber
 
 
Posts: 25
Joined: Thu May 15, 2003 4:21 pm
Location: Indianapolis

Re: Quick XOR question

Postposted on 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:
Code: Select all
if ((i == 0) != (j == 0)) {
  // exactly one of i or j is zero
} else {
  // they are either both zero, or both non-zero
}
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37659
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Quick XOR question

Postposted on Wed Sep 21, 2011 6:27 pm

Code: Select all
if (i*j == 0) && (i+j != 0)
 


don't do this, I'm just being silly.
Fernando!
Your mother ate my dog!
cheesyking
Minister of Gerbil Affairs
 
Posts: 2253
Joined: Sun Jan 25, 2004 7:52 am
Location: That London (or so I'm told)

Re: Quick XOR question

Postposted on 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
SecretSquirrel
Gerbil Jedi
Gold subscriber
 
 
Posts: 1704
Joined: Tue Jan 01, 2002 7:00 pm
Location: The Colony, TX (Dallas suburb)

Re: Quick XOR question

Postposted on 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
Sapphire Radeon 6950
TurtlePerson2
Graphmaster Gerbil
 
Posts: 1097
Joined: Sat May 26, 2007 9:08 am
Location: Plano, Texas

Re: Quick XOR question

Postposted on 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).
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37659
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: Quick XOR question

Postposted on 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 :(
morphine
Gerbil Khan
Silver subscriber
 
 
Posts: 9954
Joined: Fri Dec 27, 2002 8:51 pm
Location: Portugal (that's next to Spain)

Re: Quick XOR question

Postposted on 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...
notfred
Grand Gerbil Poohbah
 
Posts: 3730
Joined: Tue Aug 10, 2004 10:10 am
Location: Ottawa, Canada


Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 0 guests