Swapping two variable value without using third variable
One of the very tricky questions asked in an interview.
Swap the values of two variables like a=10 and b=15.
Generally to swap two variables values, we need 3rd variable like:
temp=a;
a=b;
b=temp;
N开发者_如何转开发ow the requirement is, swap values of two variables without using 3rd variable.
Using the xor swap algorithm
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
Why the test?
The test is to ensure that x and y have different memory locations (rather than different values). This is because (p xor p) = 0 and if both x and y share the same memory location, when one is set to 0, both are set to 0.
When both *x and *y are 0, all other xor operations on *x and *y will equal 0 (as they are the same), which means that the function will set both *x and *y set to 0.
If they have the same values but not the same memory location, everything works as expected
*x = 0011
*y = 0011
//Note, x and y do not share an address. x != y
*x = *x xor *y //*x = 0011 xor 0011
//So *x is 0000
*y = *x xor *y //*y = 0000 xor 0011
//So *y is 0011
*x = *x xor *y //*x = 0000 xor 0011
//So *x is 0011
Should this be used?
In general cases, no. The compiler will optimize away the temporary variable and given that swapping is a common procedure it should output the optimum machine code for your platform.
Take for example this quick test program written in C.
#include <stdlib.h>
#include <math.h>
#define USE_XOR
void xorSwap(int* x, int *y){
if ( x != y ){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
void tempSwap(int* x, int* y){
int t;
t = *y;
*y = *x;
*x = t;
}
int main(int argc, char* argv[]){
int x = 4;
int y = 5;
int z = pow(2,28);
while ( z-- ){
# ifdef USE_XOR
xorSwap(&x,&y);
# else
tempSwap(&x, &y);
# endif
}
return x + y;
}
Compiled using:
gcc -Os main.c -o swap
The xor version takes
real 0m2.068s
user 0m2.048s
sys 0m0.000s
Where as the version with the temporary variable takes:
real 0m0.543s
user 0m0.540s
sys 0m0.000s
the general form is:
A = A operation B
B = A inverse-operation B
A = A inverse-operation B
however you have to potentially watch out for overflows and also not all operations have an inverse that is well defined for all values that the operation is defined. e.g. * and / work until A or B is 0
xor is particularly pleasing as it is defined for all ints and is its own inverse
a = a + b
b = a - b // b = a
a = a - b
No-one has suggested using std::swap, yet.
std::swap(a, b);
I don't use any temporary variables and depending on the type of a and b the implementation may have a specalization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not. There's no point in trying to second guess.
More generally, I'd probably want to do something like this, as it would work for class types enabling ADL to find a better overload if possible.
using std::swap;
swap(a, b);
Of course, the interviewer's reaction to this answer might say a lot about the vacancy.
As already noted by manu, XOR algorithm is a popular one which works for all integer values (that includes pointers then, with some luck and casting). For the sake of completeness I would like to mention another less powerful algorithm with addition/subtraction:
A = A + B
B = A - B
A = A - B
Here you have to be careful of overflows/underflows, but otherwise it works just as fine. You might even try this on floats/doubles in the case XOR isn't allowed on those.
Stupid questions deserve appropriate answers:
void sw2ap(int& a, int& b) {
register int temp = a; // !
a = b;
b = temp;
}
The only good use of the register keyword.
Swapping two numbers using third variable be like this,
int temp;
int a=10;
int b=20;
temp = a;
a = b;
b = temp;
printf ("Value of a", %a);
printf ("Value of b", %b);
Swapping two numbers without using third variable
int a = 10;
int b = 20;
a = a+b;
b = a-b;
a = a-b;
printf ("value of a=", %a);
printf ("value of b=", %b);
#include<iostream.h>
#include<conio.h>
void main()
{
int a,b;
clrscr();
cout<<"\n==========Vikas==========";
cout<<"\n\nEnter the two no=:";
cin>>a>>b;
cout<<"\na"<<a<<"\nb"<<b;
a=a+b;
b=a-b;
a=a-b;
cout<<"\n\na="<<a<<"\nb="<<b;
getch();
}
Since the original solution is:
temp = x; y = x; x = temp;
You can make it a two liner by using:
temp = x; y = y + temp -(x=y);
Then make it a one liner by using:
x = x + y -(y=x);
Of course, the C++ answer should be std::swap.
However, there is also no third variable in the following implementation of swap:
template <typename T>
void swap (T &a, T &b) {
std::pair<T &, T &>(a, b) = std::make_pair(b, a);
}
Or, as a one-liner:
std::make_pair(std::ref(a), std::ref(b)) = std::make_pair(b, a);
If you change a little the question to ask about 2 assembly registers instead of variables, you can use also the xchg operation as one option, and the stack operation as another one.
Consider a=10, b=15:
Using Addition and Subtraction
a = a + b //a=25
b = a - b //b=10
a = a - b //a=15
Using Division and multiplication
a = a * b //a=150
b = a / b //b=10
a = a / b //a=15
#include <iostream>
using namespace std;
int main(void)
{
int a,b;
cout<<"Enter a integer" <<endl;
cin>>a;
cout<<"\n Enter b integer"<<endl;
cin>>b;
a = a^b;
b = a^b;
a = a^b;
cout<<" a= "<<a <<" b="<<b<<endl;
return 0;
}
Update: In this we are taking input of two integers from user. Then we are using the bitwise XOR operation to swap them.
Say we have two integers a=4 and b=9 and then:
a=a^b --> 13=4^9
b=a^b --> 4=13^9
a=a^b --> 9=13^9
Here is one more solution but a single risk.
code:
#include <iostream>
#include <conio.h>
void main()
{
int a =10 , b =45;
*(&a+1 ) = a;
a =b;
b =*(&a +1);
}
any value at location a+1 will be overridden.
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
a ^= b;
b ^= a;
a ^= b;
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
that's the correct XOR swap algorithm
void xorSwap (int* x, int* y) {
if (x != y) { //ensure that memory locations are different
if (*x != *y) { //ensure that values are different
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
}
you have to ensure that memory locations are different and also that the actual values are different because A XOR A = 0
You may do....in easy way...within one line Logic
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a^b^(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
or
#include <stdio.h>
int main()
{
int a, b;
printf("Enter A :");
scanf("%d",&a);
printf("Enter B :");
scanf("%d",&b);
int a = 1,b = 2;
a=a+b-(b=a);
printf("\nValue of A=%d B=%d ",a,b);
return 1;
}
public void swapnumber(int a,int b){
a = a+b-(b=a);
System.out.println("a = "+a +" b= "+b);
}
The best answer would be to use XOR and to use it in one line would be cool.
(x ^= y), (y ^= x), (x ^= y);
x,y are variables and the comma between them introduces the sequence points so it does not become compiler dependent. Cheers!
Let's see a simple c example to swap two numbers without using the third variable.
program 1:
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a+b;//a=30 (10+20)
b=a-b;//b=10 (30-20)
a=a-b;//a=20 (30-10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
Output:
Before swap a=10 b=20 After swap a=20 b=10
Program 2: Using * and /
Let's see another example to swap two numbers using * and /.
#include<stdio.h>
#include<conio.h>
main()
{
int a=10, b=20;
clrscr();
printf("Before swap a=%d b=%d",a,b);
a=a*b;//a=200 (10*20)
b=a/b;//b=10 (200/20)
a=a/b;//a=20 (200/10)
printf("\nAfter swap a=%d b=%d",a,b);
getch();
}
Output:
Before swap a=10 b=20 After swap a=20 b=10
Program 3: Making use of bitwise XOR operator:
The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number which has all the bits as 1 wherever bits of x and y differ. For example, XOR of 10 (In Binary 1010) and 5 (In Binary 0101) is 1111 and XOR of 7 (0111) and 5 (0101) is (0010).
#include <stdio.h>
int main()
{
int x = 10, y = 5;
// Code to swap 'x' (1010) and 'y' (0101)
x = x ^ y; // x now becomes 15 (1111)
y = x ^ y; // y becomes 10 (1010)
x = x ^ y; // x becomes 5 (0101)
printf("After Swapping: x = %d, y = %d", x, y);
return 0;
Output:
After Swapping: x = 5, y = 10
Program 4:
No-one has suggested using std::swap, yet.
std::swap(a, b);
I don't use any temporary variables and depending on the type of a and b the implementation may have a specialization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not.
Problems with above methods:
1) The multiplication and division based approach doesn’ work if one of the numbers is 0 as the product becomes 0 irrespective of the other number.
2) Both Arithmetic solutions may cause arithmetic overflow. If x and y are too large, addition and multiplication may go out of integer range.
3) When we use pointers to a variable and make a function swap, all of the above methods fail when both pointers point to the same variable. Let’s take a look what will happen in this case if both are pointing to the same variable.
// Bitwise XOR based method
x = x ^ x; // x becomes 0
x = x ^ x; // x remains 0
x = x ^ x; // x remains 0
// Arithmetic based method
x = x + x; // x becomes 2x
x = x – x; // x becomes 0
x = x – x; // x remains 0
Let us see the following program.
#include <stdio.h>
void swap(int *xp, int *yp)
{
*xp = *xp ^ *yp;
*yp = *xp ^ *yp;
*xp = *xp ^ *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Output:
After swap(&x, &x): x = 0
Swapping a variable with itself may be needed in many standard algorithms. For example, see this implementation of QuickSort where we may swap a variable with itself. The above problem can be avoided by putting a condition before the swapping.
#include <stdio.h>
void swap(int *xp, int *yp)
{
if (xp == yp) // Check if the two addresses are same
return;
*xp = *xp + *yp;
*yp = *xp - *yp;
*xp = *xp - *yp;
}
int main()
{
int x = 10;
swap(&x, &x);
printf("After swap(&x, &x): x = %d", x);
return 0;
}
Output:
After swap(&x, &x): x = 10
Maybe off topic, but if you know what you are swapping a single variable between two different values, you may be able to do array logic. Each time this line of code is run, it will swap the value between 1 and 2.
n = [2, 1][n - 1]
You could do:
std::tie(x, y) = std::make_pair(y, x);
Or use make_tuple when swapping more than two variables:
std::tie(x, y, z) = std::make_tuple(y, z, x);
But I'm not sure if internally std::tie uses a temporary variable or not!
In javascript:
function swapInPlace(obj) {
obj.x ^= obj.y
obj.y ^= obj.x
obj.x ^= obj.y
}
function swap(obj) {
let temp = obj.x
obj.x = obj.y
obj.y = temp
}
Be aware to execution time of both options.
By run this code i measured it.
console.time('swapInPlace')
swapInPlace({x:1, y:2})
console.timeEnd('swapInPlace') // swapInPlace: 0.056884765625ms
console.time('swap')
swap({x:3, y:6})
console.timeEnd('swap') // swap: 0.01416015625ms
As you can see (and as many said), swap in place (xor) take alot time than the other option using temp variable.
R is missing a concurrent assignment as proposed by Edsger W. Dijkstra in A Discipline of Programming, 1976, ch.4, p.29. This would allow for an elegant solution:
a, b <- b, a # swap
a, b, c <- c, a, b # rotate right
How about,If we do with parallel processing with "GO" lang..
var x = 100; var y = 200;
swap1 := func(var i) { x = i } swap2 := func(var y) { y = i } Parallelize(swap1, swap2)
Try this code: (sample in php)
$a = 5;
$b = 7;
echo $a .' ***Before*** '. $b;
$a = $a + $b; //12
$b = $a - $b; //12 - 7 = 5
$a = $a - $b; //12 - 5 = 7
echo $a .' ***After*** '. $b;
UPDATE :: a demo of what the effects are for the 3 types of swapping methods available in awk
— (awk doesn't offer true bit-wise XOR) :
either
substr() wrapperorfunction and/or arrayare truly lossless for any input, even when swapping arbitrary binary data ingawk unicode-mode,or when swapping completely different data types, like a unicode string with an approximation of euler's
ethat's beyondIEEE 754double-prec floating point precisionarithmetic-based swapsare only lossless when both inputs are actually numeric, not potentially subject to special interpretation rules, e.g. built-in hex decoding in someawkvariants when you place a unary+or-in front of it, AND both inputs are entirely within the current precision level.USE IT WITH CAUTION
echo '91223951291111 '\
'8777175273333\n' \
\
'abc@\uF8FF_123^456#\0306\02222\\|/<>[]{\0354\0210\0657}()&+- '\
'2.7182818284590452353602874713526624977
5724709369995957496696762772407663035
35475945713821785251\n' \
\
'FTX_ThreeArrows_Luna_Terra ' \
'abc345\0301\0375fgc' |
LANG='en_US.UTF-8' LC_ALL= gawk -e '
BEGIN {
1 __________ = "\f\r\t\t..."
} {
3 split(_=__=___ = "",____)
}
{
3 print ">ORIGINAL_INPUT :: ", _ = $++__,
__________, __ = $++__,
"\n--------------- :: --------------"\
"--------------\n"
3 _ = __ substr("", (__=_)^(_<_))
3 print "substr(..)-swap :: ", _, __________, __
3 ____[++___] = _
3 ____[++___] = __
3 swap(____)
3 __ = ____[___--]
3 _ = ____[___--]
3 print "func+array-swap :: ",_,__________,__
3 _ -= __ = (_+=__) - __
3 print "arithmetic-swap :: ",_,__________,__
3 print "__________"
}
function swap(__,_,___) {
___ = __[++_]
__[_] = __[_+_]
__[_+_] = ___
}'
>ORIGINAL_INPUT :: 91223951291111
... 8777175273333
--------------- :: -------------- --------------
substr(..)-swap :: 8777175273333
... 91223951291111
func+array-swap :: 91223951291111
... 8777175273333
arithmetic-swap :: 8777175273333
... 91223951291111
__________
>ORIGINAL_INPUT :: abc@_123^456#ƒ2\|/<>[]{숯}()&+-
... 2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251
--------------- :: -------------- --------------
substr(..)-swap :: 2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251
... abc@_123^456#ƒ2\|/<>[]{숯}()&+-
func+array-swap :: abc@_123^456#ƒ2\|/<>[]{숯}()&+-
... 2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251
arithmetic-swap :: 2.71828
... 0
__________
>ORIGINAL_INPUT :: FTX_ThreeArrows_Luna_Terra
... abc345??fgc
--------------- :: -------------- --------------
substr(..)-swap :: abc345??fgc
... FTX_ThreeArrows_Luna_Terra
func+array-swap :: FTX_ThreeArrows_Luna_Terra
... abc345??fgc
arithmetic-swap :: 0
... 0
__________
In awk, without needing a temp variable, a temp array, an external function call, substring-ing their values out of one another, XOR operations, or even any math operations of any sort,
this trick works for whether their values are numeric, string, or even arbitrary bytes that aren't UTF8-compliant, nor do the types of the 2 variables even need to match :
gawk/mawk/nawk '{
a = (b) \
substr("", ( b = (a) )^"")
}'
Even in Unicode-locale, gawk unicode mode could swap the values of arbitrary non-UTF8 bytes without any error messages.
No need to use C or POSIX locale.
Why it works is that in the process of this concatenation, the original value of b has already been placed in some system-internal staging ground, so the sub-sequent assignment of b's value into a does not have any impact into what's being assigned into a
The second half of it is taking a substring of an empty string, so of course nothing comes out, and doesn't affect the first half.
After b = a, I immediately take the zero-th power of it, which always returns a 1 in awk
so the latter portion becomes
# in awk, string indices start from 1 not 0
substr(EMPTY_STRING, STARTING-POSITION-OF-ONE)
of course nothing comes out of it, which is the desired effect, so the clean original value of b could be assigned into a.
This isn't taking a substring of a's or b's value. It's taking advantage of dynamic typing properties of awk.
A XOR-based approach, which clean, still require 3 operations, plus a safety check against being memory position (for C). And for gnu-awk, its xor() function only works with non-negative numeric inputs.
This one-liner approach circumvents all the common issues with value swapping.
Either a or b, or even both, being an array cell, regardless of single or multi-dimensional, e.g.
arr[ _pos_idx_a_ ]
works exactly the same with this one-liner approach. The only limitation I could think of is that this approach cannot directly swap full contents of an entire array with another array.
I thought of adding a check for a==b to avoid a double assignment, but then realized the internal system resources needed to perform such a check is not worth the minuscule amount of time saved.
a = a + b - (b=a);
It's very simple, but it may raise a warning.
single line solution for swapping two values in c language.
a=(b=(a=a+b,a-b),a-b);
second_value -= first_value;
first_value += second_value;
second_value -= first_value;
second_value *= -1;
加载中,请稍侯......
精彩评论