Printable View
I sure most of u know C programming...
The question is not anything related to C programming. Its about ur logical thinking.
Question? : Swap two integers without using third variable???
I know there are lot of methods to do this... But my main question which method is optimised one and the reason for that???
Assume the numbers to be a& b
a=a+b
b=a-b (Now b= a+b-b= a)
a=a-b (Now a = a+b - a=b)
As simple as that.
(Believe me, this is the most effecient method out there. I can prove it if someone comes with any other solution:D )
Cheers!
Kalayama
Alright let me post another way of solving the problem.
As usual, let the numbers to be swapped be a&b.
a=a*b
b=a/b (Now, b =(a*b)/b = a)
a=a/b (Now, a =(a*b)/a = b)
Now, according to me, the second method is fr too inferior comared to my previous post. (I can justify that:D )
Any other solutions possible???? I'm still thinking...
Cheers!
Kalayama
Yes Kalayama...
Both the solutions are correct but there is one more solution also... The third solution is very optimized...
For the above solutions your answer is right... First one is more optimized... Can u justify that...
1) If one of the numbers is "zero" then second method won't work.
2) Multiplication and division take much more CPU time than addition and substraction.
3) In programming, there is "out of bound" condition, which will be satisfied much earlier in the second method which makes it all the less effecient (For example if a=3 and b=32000, the first method will execute successfully in C/C++, but second will fail as the product a*b will exceed the upper cut off for integer which is (for unsigned) 2^16-1 = 65535. For signed it is still worse having a cut off of 12767)
Aren't they good enough reasons????
I'm still thinking of a third method though...:D
Cheers!
Kalayama
Very Good Kalayama!!!
There is one more reason is also there...
In CPU there is no separate unit for multiplication and division... but there are units for addition and substraction... In CPU's multiplication is carried out by repeated addition...
This reason is somewat fine tuning ur second reason...
Can u find out the third solution???
Here is one more solution....
a = a ^ b;
b = b ^ a;
a = a ^ b;
I didn't know this is the optimized one....i got it through one of my friend...
------------------
suresh
It is not entirely true that there is no multiplication unit in CPU. There are CPU's that come with multiplication units. For example, any DSP processor will definitely have an in built multiplier. As far as I know, even pentium series had a multiplier embedded in them.
But still, Multiplication takes atleast aroud 8 times more time than addition.
I'm focusing on a lot of items now. This problem is running in the background. May be you can give me some clue:cool: I might be able to solve it faster. Or just waite for some more time:p
Cheers!
-Kalayama
Yes Kalayama u r absolutely right... But the problem is we are not using any DSP processors in computers. One of the reason for this DSP processors are damn costly. The purpose of DSP processors is to replace the Analog IC. In Computers we are not using any analog signals. But sure in mobile phones and all DSP processors rules...
And one more thing Kalayama that in DSP u cannot say multiplication is slower than addition... There are DSP units which does multiplication with the same speed that of addition... It depends on what kind of multiplier architecture they are implementing in the DSP unit...
Congrats Suresh u got the third solution,
a=a xor b
b=a xor b
a=a xor b
all are bit-wise XOR... this is very optimised one than other two solutions...
When we use first two method there is a possibility of Interger-Overflow...
But I recommend u guys not to use these methods in your programs unless otherwise there is serious memory constraint... Because swap using temporary variable is very faster than those three... U guys know that now a days time is a critical factor not memory...
What if one of the numbers is negtive? Won't the answers b n two's compliment form?(I haven't tried this through compiler. Just wtd to ask here, be for I run it there).
-Kalayama
It will work for negative numbers too...
You can try this out in any of the compilers...
Guys i dont know anything about c:D.ive joined in btech mechanical 2 days ago in GITAM.in 1 class a mam asked us 2 write an algorithm 2 swap two no.s.Then i used the following logic:
Consider 2 nos. a,b
CASE1
If a<b(let a=20 b=50).
Step1:Calculate b-a which in this case is 30.
Step2: Do a+(b-a) and b-(b-a).
CASE2
If a>b(let a=50 b=20).
Step1:Calculate a-b which int this case is 30.
Step2: Do a-(a-b) and b+(a-b)
THE NUMBERS HAVE BEEN SWAPPED.AM I RIGHT?
But why cant a computer simply swap the nos?eh?why cant it do like we do???