Win a copy of Machine Learning Systems: Designs that scale this week in the Scala forum
or Xamarin in Action: Creating native cross-platform mobile apps in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Odd Occurrences In Array  RSS feed

 
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:I'm not sure if I can give any more hints without just giving it away, so I might as well just post the answer:



XOR , how did you think about that ? i really want to learn
 
Saloon Keeper
Posts: 8878
166
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Because I've used XOR before to solve similar problems. Effective Java by Joshua Bloch also quotes a snipped of code that some C programmers would use to swap two variables without using a temporary variable:
This will not work in Java, because Java performs strict left-to-right evaluation. This however will:
 
Ranch Hand
Posts: 1149
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Because I've used XOR before to solve similar problems. Effective Java by Joshua Bloch also quotes a snipped of code that some C programmers would use to swap two variables without using a temporary variable:
This will not work in Java, because Java performs strict left-to-right evaluation. This however will:



How about...


A single test case worked for me, so it must be correct.

Slightly more elegant than my single-line version, but arguably better than the three-line solution:

 
Stephan van Hulst
Saloon Keeper
Posts: 8878
166
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it's a nice parlor trick, but there's no reason to avoid writing the swap that uses a temporary variable, which most people will understand instantly.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:I think it's a nice parlor trick.


It's not just a parlour trick; it actually has many applications - such as fault-tolerance (specifically RAID5), cryptography, and graphics (it was one of the early ways of creating a mouse pointer or "floating cursor" - don't know if it's still used for that now or not).

It was also the method old computers used to use to 'zero' memory (because x ^ x == 0). Again, I don't know if it's still used for that now or not.

The reason for its use in cryptography is that there is no "un-XOR" function - that is: given x ^ y, there is no way to determine x or y without guessing if you don't know either of them (and hence the need for passwords to be secret).

It's also blisteringly fast - usually operating in a single machine cycle.

I can't believe I didn't spot it myself (until Stephan's post a while back) because it was one of the first things I thought of; but I didn't follow it through logically. Just stupid I guess.

Winston
 
Stephan van Hulst
Saloon Keeper
Posts: 8878
166
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I meant swapping two variables without using a temporary variable, not the use of XOR in general
 
Squanch that. And squanch this tiny ad:
Rocket Oven Kickstarter - from the trailboss
https://coderanch.com/t/695773/Rocket-Oven-Kickstarter-trailboss
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!