• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Odd Occurrences In Array

 
Greenhorn
Posts: 23
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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:
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I meant swapping two variables without using a temporary variable, not the use of XOR in general
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic