|
|
| |
Terms of Agreement:
By using this article, you agree to the following terms...
1) You may use
this article in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
2) You MAY NOT redistribute this article (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
3) You may link to this article from another website, but ONLY if it is not wrapped in a frame.
4) You will abide by any additional copyright restrictions which the author may have placed in the article or article's description. | Swap Two ints Without Using a Third Variable
Here's an old trick from C, which carries over to
Java. If you have two ints a and b whose
values you want to swap, the obvious way to
do so is with a third, temporary variable:
int c = a;
a = b;
b = c;
It can be done without a temporary variable,
however, using Java's bitwise xor operator ^:
a = a^b;
b = a^b;
a = a^b;
The operator ^ produces a new int, each of whose
bits is the result of xor-ing the two
corresponding bits from the operands (1 if
the bits are different, 0 otherwise). To see why the trick works, consider the single-bit case
of a=1 and b=0.
a = a^b = 1 xor 0 = 1
b = a^b = 1 xor 0 = 1
a = a^b = 1 xor 1 = 0
Even though you initially overwrite the value of
a, no information is lost; its encoding
simply changes. In the case of larger (multi-bit)
numbers, each pair of bits will be swapped
in the same way, and so the entire int values are swapped.
Finally, the swapping code can be made even more
succinct:
a ^= b ^= a ^= b;
| |
Other 12 submission(s) by this author
|
|
| |
| Report Bad Submission |
|
| |
| Your Vote! |
|
See Voting Log |
| |
| Other User Comments |
8/10/2003 9:24:52 PM:Frenzied-Panda
Thank You for posting this code
:D.
You dont know how usefull this is
to me.
I tested this with a long
varible FFFF * FFFF times :D it was
perfect
Thanks for the code
|
8/11/2003 5:26:40 AM:Alaeddin Hallak
Brilliant
|
8/12/2003 7:34:05 AM:
There is some simple way which may
apply to (virtually) any
language:
a=a+b
b=a-b
a=a-b
|
8/15/2003 3:59:16 PM:
Nice article, but you should ask
yourself a question: Which is better,
using a third variable, using XOR, or
using subtraction? Take a look at this
article to see the difference:
http://www.informit.com/isapi/guide~cplu
splus/seq_id~140/guide/content.asp
By
the way, the subraction algorithms
appears to work with large and small
numbers equivalently. I tested it using
the values 6 and 10, 0xFFFFFFFF and 0,
0xFFFFFFFA and 0xFFFFFFFB.
|
8/16/2003 8:05:14 AM:
I knew about this algorithm, but for
some reason, I never thought about
simplifying it. 1 line! Brilliant!
|
8/16/2003 4:29:27 PM:Šonny Nadolny
If any of you want to know the best way
of swapping two variables, I wrote a
program to test 4 different ways of
swapping and show how long they took
(the 4 ways being XOR,
addition/subtraction, using a temp
variable and declaring it each swap,
and using a temp variable only
declaring it once). Here's the code:
http://www.pscode.com/vb/scripts/ShowCod
e.asp?txtCodeId=3824&lngWId;=2
|
8/16/2003 4:34:52 PM:Šonny Nadolny
Sorry, that link is messed up... this
one should work:
http://www.pscode.com/vb/scripts/
ShowCod e.asp?txtCodeId=3824&lngWId;=2
|
8/20/2003 1:52:38 AM:MarK
thxn for simple approach - never struck
me this way! :)
|
9/3/2003 12:04:59 PM:
I think this algorythm is for less
resource intence languages, like C or
assembler. chances are that java is
alocating some space for the xor's
anyway and so the savings is not really
acheived. but hey I like programming
in C, so thanks for the hint!
|
|
| Add Your Feedback! |
Note:Not only will your feedback be posted, but an email will be sent to the code's author in your name.
NOTICE: The author of this article has been kind enough to share it with you. If you have a criticism, please state it politely or it will be deleted.
For feedback not related to this particular article, please click here.
|
|
