Bubble.ro - because there is always something new to learn about

Interchanging 2 variables without the use of a third

 

Category: Programming/PHP

There are several ways Iíve seen over the years of interchanging 2 variables. Iíll show you here how you can do it with bitwise operations. This method is most efficient when used in combination with assembler. In C++ it is looked at more like a curiosity than a real method by most. However if you would want to make your C++ code harder to read, then this can be helpful.

    A byte of theory

     Before seeing how we can interchange two variables we will have to learn the use of the XOR logical operator. It is sometimes called exclusive OR, or exclusive disjunction. It is true when one of the operands (the numbers between which we are using XOR) is true, but not both, while its close brother the OR operator is true even when both are true.

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0


    You can remember it more easily if you think of it like adding binary numbers without carry. So: 0+0=0 ; 0+1=1 ; 1+0=1 ; 1+1=0 carry 1. So by ignoring the carry we obtain the XOR logical function.

    So how can we use it?

Let’s say that we have two variables say a=5 and b=3. The steps we would have to take to switch the two variables (registers) are shown in the table below:

a 0101
b 0011
a = a XOR b 0110
b = a XOR b 0101
a = a XOR b 0011


    i)    In assembler ( asm )

Let’s suppose that a and b are in two of the CPU registers: AL and respectively BL.

The coding sequence looks like this:

;AL contains 0101, BL contains 0011

XOR AL, BL            ; AL will receive the result of the operation: 0110
XOR BL, AL            ; BL will contain 0101, the starting value of AL
XOR AL, BL            ; after this XOR with BL, AL will receive 0011     

Note: As you can see the XOR operator in ASM delivers the result of the operation in the first register you mention.


    ii)    In C/C++

In C++ the XOR operator is represented by the operator "^" (without the quotes). So the coding sequence for C++ is:

main(){

int a=5;
int b=3;

a = a ^ b;    // a will contain a xor b = 6
b = a ^ b;    // b will receive 6 xor 3 = 5
a = a ^ b;    // a will become 6 xor 5 = 3

printf("a=%d b=%d", a,b);
}

By using the operator ^= we could make our code harder to read :

main(){

int a=5;
int b=3;

a ^= b;    // a will contain a xor b = 6
b ^= b;    // b will receive 6 xor 3 = 5
a ^= b;    // a will become 6 xor 5 = 3

printf("a=%d b=%d", a,b);
}

    In the end I would like to mention another interesting use of the XOR function especially for ASM. If we want to empty a register (let’s say AL) we would use "XOR AL, AL". So by XORing a number with itself we obtain 0 because 0 xor 0 = 0 and 1 xor 1 = 0.

Posted by: Nitro on September 16, 2006 at 05:30.
 

» Comments

Other ways
There are other methods for this:

a = a * b
b = a / b
a = a / b

Posted by Gerard on September 16, 2006 at 06:45 AM.

Re: Other ways
There are indeed other ways as well, but they use more processor cycles usually. Xor is efficient simply because it uses a single processor cycle and can't cause any range overflow. Also, the method above is efficient because it uses a single operation, which makes it easier to integrate into specialised microprocessors for example.

Another method with similar performaces can be using:

a = a + b
b = a - b
a = a - b

But then again, this needs two operations (sum and difference - which can be made with negation and another sum), but it still uses more cycles than a simple xor.

Posted by Indy on September 16, 2006 at 08:32 AM.

Not Other Ways
The two other ways noted above presuppose that variable a has sufficient bits available to store the sum or product of a and b.

The original method does not have this restriction.

Posted by Mike on October 27, 2006 at 09:39 AM.

Add and subtract just have to be invertible no actually capable of preserving the intermediate range
title says it all

Posted by Anon Ymous on October 31, 2006 at 06:32 PM.

Type
Actually, it's:

a ^= b;
b ^= a;
a ^= b;

Posted by Larry on December 19, 2009 at 02:27 PM.

post o post
currently, actually no idea

Posted by want to say ya on August 25, 2010 at 04:59 AM.

Random Article


Search


Feeds


Bubble.ro RSS Feed

All Categories


Articles


Aetolia - The Midnight Age
How to create the histogram of an image using PHP
How to convert an image to grayscale using PHP
How to check if an image is grayscale in PHP
Interchanging 2 variables without the use of a third
Error launching browser window:no XBL binding for browser
Convert the AOL user session collection to a MySQL database
Introduction to Matlab
Creating a customized session handling system in PHP (part II)
Creating a customized session handling system in PHP (part I)
Firefox crashing with Yahoo! Messenger
ADL Search for oDC
Video codecs explained
Browsershots
How to use Auto-Away Message with oDC
Create complete Windows XP disk with SP2 and all updates
Data Execution Prevention error message in Windows XP
Google Mars
Logarithmic scale graphs in Excel
Urban Dictionary (or wtf does l33t mean?)
Learn more about BIOS
Backup your Firefox and Thunderbird settings
Syndicate your Yahoo 360 profile
What is Google PageRank?
'Cannot Open the File: Mk:@MSITStore' Error Message
Get your Gmail with Mozilla Thunderbird
E-Books links
Change the size of your Explorer thumbnails
Remove previews from Windows Explorer
How can I turn off system beeps?
How do I disable Internet Explorer?
What are proxies or how do I protect my anonymity?
How to set aliases triggers or macros in MushClient
What is RSS?
Palm Zire 31 fast review
oDC Installation and Basic Configuration
How I built a 2x80W amplifier (using power modules)
Leech/HotLink Protection
How to block referrer detection?
How to find out your IP address
Getting started with Mushclient
What is spyware and how do I protect my PC from it?
Stumble Upon - random surfing around the web
Automatic file backup for Windows users
How can I read foreign language sites?
Protect your web surfing privacy!
What is BitTorrent?
No more ads! Adblock for Firefox
Why use Firefox instead of Internet Explorer?
How do I create my own Yahoo ID?
© Copyright 2006-2017 Bubble. All rights reserved. Sitemap - Contact