Programming
-
- Posts: 1958
- Joined: Thu Apr 03, 2008 10:02 pm
- Location: Beyond the Mountains of the Copper Miners into the Desert of Absolute Boredom
- Contact:
Programming
Fred, my TA's are crazy. If you have two variables while programming in C, X and Y, and you want to exchange their values but cannot use a temporary variable, how would you do it?
I would say something like
int x, y;
{
x=x+y; y=x-y; x=x-y;
}
But the TA's say that would not work with latch numbers, but that somehow doing this works:
int x, y;
{
y=x^y;
x=x^y;
y=x^y;
}
This assumes that x and y are initialized and all that... so am I right or how would it be done?
I would say something like
int x, y;
{
x=x+y; y=x-y; x=x-y;
}
But the TA's say that would not work with latch numbers, but that somehow doing this works:
int x, y;
{
y=x^y;
x=x^y;
y=x^y;
}
This assumes that x and y are initialized and all that... so am I right or how would it be done?
-
- Never Coming Back?
- Posts: 2031
- Joined: Mon Apr 02, 2007 9:59 am
- Location: Provo, UT
- Contact:
-
- Never Coming Back?
- Posts: 2031
- Joined: Mon Apr 02, 2007 9:59 am
- Location: Provo, UT
- Contact:
-
- Posts: 1958
- Joined: Thu Apr 03, 2008 10:02 pm
- Location: Beyond the Mountains of the Copper Miners into the Desert of Absolute Boredom
- Contact:
-
- Posts: 1958
- Joined: Thu Apr 03, 2008 10:02 pm
- Location: Beyond the Mountains of the Copper Miners into the Desert of Absolute Boredom
- Contact:
ah.. never heard such a term.
so lets say for a 4 bit number using 2s compliment...
x = 7 = 0111
y = -8 = 1000
x = x + y = 0111 + 1000 = 1111 = -1
y = x - y = 1111 - 1000 = 1111 + 1000 = 0111 = 7
x = x - y = 1111 - 0111 = 1111 + 1001 = 1000 = -8
so that worked.....
x = -1 = 1111
y = -8 = 1000
x = x + y = 1111 + 1000 = 0111 = 7
y = x - y = 0111 - 1000 = 0111 + 1000 = 1111 = -1
x = x - y = 0111 - 1111 = 0111 + 0001 = 1000 = -8
hmm... did they give you the case where it doesn't work?
so lets say for a 4 bit number using 2s compliment...
x = 7 = 0111
y = -8 = 1000
x = x + y = 0111 + 1000 = 1111 = -1
y = x - y = 1111 - 1000 = 1111 + 1000 = 0111 = 7
x = x - y = 1111 - 0111 = 1111 + 1001 = 1000 = -8
so that worked.....
x = -1 = 1111
y = -8 = 1000
x = x + y = 1111 + 1000 = 0111 = 7
y = x - y = 0111 - 1000 = 0111 + 1000 = 1111 = -1
x = x - y = 0111 - 1111 = 0111 + 0001 = 1000 = -8
hmm... did they give you the case where it doesn't work?
Both will work in C/C++ provided you are working with ints or int pointers. (with some caveats I'll point out later)
If you try with other variable types you might get implied type-casting or other un-expected behavior which could screw with your variables values before and after the operation. (like floats / chars / etc...) This is compiler dependent... so what may work on GCC won't behave the same on Intel's compiler...
The XOR method is, however, superior to addition/subtraction in that it can account for overflow...
i.e. If you try this with the following numbers:
x = 4294967295;
y = 1;
x = x + y = 4294967296 (which requires 33-bits to properly represent and will overflow) = ??? (undefined behavior here...)
So if the computer just chops off the 33nd bit... you get 0... so...
x = 0
y = 0 - 1 = -1
x = 0 - (-1) = 1
Using the XOR method we get
x = 11111111111111111111111111111111b
y = 00000000000000000000000000000001b
y = x ^ y = 11111111111111111111111111111110b
x = x ^ y = 00000000000000000000000000000001b
y = x ^ y = 11111111111111111111111111111111b
So although the addition and subtraction will work in most cases... XOR works 100%
I think I may have screwed up that example... but whatever... you get the idea...
If you try with other variable types you might get implied type-casting or other un-expected behavior which could screw with your variables values before and after the operation. (like floats / chars / etc...) This is compiler dependent... so what may work on GCC won't behave the same on Intel's compiler...
The XOR method is, however, superior to addition/subtraction in that it can account for overflow...
i.e. If you try this with the following numbers:
x = 4294967295;
y = 1;
x = x + y = 4294967296 (which requires 33-bits to properly represent and will overflow) = ??? (undefined behavior here...)
So if the computer just chops off the 33nd bit... you get 0... so...
x = 0
y = 0 - 1 = -1
x = 0 - (-1) = 1
Using the XOR method we get
x = 11111111111111111111111111111111b
y = 00000000000000000000000000000001b
y = x ^ y = 11111111111111111111111111111110b
x = x ^ y = 00000000000000000000000000000001b
y = x ^ y = 11111111111111111111111111111111b
So although the addition and subtraction will work in most cases... XOR works 100%
I think I may have screwed up that example... but whatever... you get the idea...
ah, 361, my bad, i didn't take into account unsigned integers.
so with a 4bit unsigned integers,
x = 1111 = 16
y = 1110 = 15
x = x + y = 1111 + 1110 = 0001 = 1
y = x - y = 0001 - 1110 = 0001 + 0010 = 3
x = x - y = 0001 - 0010 = 0001 + 1110 = 16
so yeah, ugly. assuming signed, 2s complement signed integers, even overflow shouldn't be an issue though as seen in my above example and here:
x = 7 = 0111
y = 1 = 0001
x = x + y = 0111 + 0001 = 1000 = -8
y = x - y = 1000 - 0001 = 1000 + 1111 = 0111 = 7
x = x - y = 1000 - 0111 = 1000 + 1001 = 0001 = 1
of course not all architectures use 2s compliment nor can we assume signed integers, so yes, the XOR is correct.
in C, there should be no difference between using a char and an integer with either of these functions. Floats are a totally different story, and XORing them would definitely not work. I don't feel like figuring out if the adding/subtracting method would.
so with a 4bit unsigned integers,
x = 1111 = 16
y = 1110 = 15
x = x + y = 1111 + 1110 = 0001 = 1
y = x - y = 0001 - 1110 = 0001 + 0010 = 3
x = x - y = 0001 - 0010 = 0001 + 1110 = 16
so yeah, ugly. assuming signed, 2s complement signed integers, even overflow shouldn't be an issue though as seen in my above example and here:
x = 7 = 0111
y = 1 = 0001
x = x + y = 0111 + 0001 = 1000 = -8
y = x - y = 1000 - 0001 = 1000 + 1111 = 0111 = 7
x = x - y = 1000 - 0111 = 1000 + 1001 = 0001 = 1
of course not all architectures use 2s compliment nor can we assume signed integers, so yes, the XOR is correct.
in C, there should be no difference between using a char and an integer with either of these functions. Floats are a totally different story, and XORing them would definitely not work. I don't feel like figuring out if the adding/subtracting method would.
-
- Posts: 1958
- Joined: Thu Apr 03, 2008 10:02 pm
- Location: Beyond the Mountains of the Copper Miners into the Desert of Absolute Boredom
- Contact:
- Giovanni Schwartz
- Posts: 3396
- Joined: Wed Mar 19, 2008 9:41 pm
-
- Never Coming Back?
- Posts: 2031
- Joined: Mon Apr 02, 2007 9:59 am
- Location: Provo, UT
- Contact:
- yellow m&m
- The Yellow One
- Posts: 649
- Joined: Mon May 21, 2007 10:01 am
- Location: my parents attic
- Contact:
- Giovanni Schwartz
- Posts: 3396
- Joined: Wed Mar 19, 2008 9:41 pm
101! Now I feel 31337.
(that 101 was lol. Intentionally written to be... Mind blank, can't think of word... Means attempting to be skilled, when your really not.)
Also, if you enjoy physics, you might like flashphysicsgames.com They have some fun ones. And some lame ones.
But mostly fun.
(that 101 was lol. Intentionally written to be... Mind blank, can't think of word... Means attempting to be skilled, when your really not.)
Also, if you enjoy physics, you might like flashphysicsgames.com They have some fun ones. And some lame ones.
But mostly fun.