-
May 17th, 2003, 09:14 AM
#1
Thread Starter
Addicted Member
C/C++ - Interesting swap function
this function just swaps two values without using a third variable to store a temp-value. Not very useful, but interesting nonetheless.
void swap(int * a, int *b)
{
a = a xor b;
b = b xor a;
a = a xor b;
}
-
May 18th, 2003, 11:27 PM
#2
You forgot the * in front of every variable... because right now it's swapping the pointers, and even those they don't get return-ed back... and in C you don't use XOR you use ^ to XOR
Code:
void swap(int *a, int *b)
{
*a = *a ^ *b;
*b = *b ^ *a;
*a = *a ^ *b;
}
-
May 19th, 2003, 08:46 AM
#3
Thread Starter
Addicted Member
Yeah
Sorry, forgot it
-
Aug 21st, 2003, 11:47 AM
#4
Lively Member
Re: C/C++ - Interesting swap function
void swap(int * a, int *b)
{
a = a xor b;
b = b xor a;
a = a xor b;
}
Take a look at this:
#define swap(x, y) x^=(y^=(x^=y))
By
Last edited by neodatatype; Aug 22nd, 2003 at 01:38 AM.
-
Sep 12th, 2003, 11:01 AM
#5
Monday Morning Lunatic
Convenient, however frequently not the most efficient method, especially on non-x86 platforms.
Also, xor is valid C++, just not valid C (i.e. the point made earlier still stands).
Note that you need to avoid clashes with the C++ Standard Library's swap() function.
I refuse to tie my hands behind my back and hear somebody say "Bend Over, Boy, Because You Have It Coming To You".
-- Linus Torvalds
-
Sep 16th, 2003, 12:35 PM
#6
parksie:
namespace CodeRonin
{
void swap...
}
But it's correct, it is definitly not the most efficient. On x86, code that gets optimized to this bit of assembly should be the best:
Code:
; Given that ebx is the first arg
; and ecx the second (both are int*)
mov eax, dword ptr [ebx]
xchg eax, dword ptr [ecx]
mov dword ptr [ebx], eax
All the buzzt
CornedBee
"Writing specifications is like writing a novel. Writing code is like writing poetry."
- Anonymous, published by Raymond Chen
Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.
-
Nov 27th, 2003, 10:25 AM
#7
Hyperactive Member
there is another way
int a; -- e.g 10
int b; -- e.g 5
a = a+b ; -- a=15,b=5
b = a-b ; -- a=15,b=10
a= a -b ; -- a= 5,b=10
swapped
-
Nov 27th, 2003, 01:40 PM
#8
Originally posted by sw_is_great
there is another way
int a; -- e.g 10
int b; -- e.g 5
a = a+b ; -- a=15,b=5
b = a-b ; -- a=15,b=10
a= a -b ; -- a= 5,b=10
swapped
Dude, that won't work everytime and can cause major problems. Plus the swap functions talked about will work with other datatypes, your's will only work on integers.
-
Nov 27th, 2003, 03:54 PM
#9
The xor will work only for integers too. And I believe sw's method works for any two integers, it would be easy to prove though.
Actually it should work for floats too.
But no matter, the tempvar approaches are still better, as they get optimized to registers or better anyway. And they work for everything that has a copy constructor.
Ok, let's see.
a = a + b;
b = a - b;
a = a - b;
Let's introduce new names
c = a + b;
d = c - b;
e = c - d;
And we want to prove that d == a and e == b.
d = (a + b) - b = a, proved.
e = (a + b) - ((a + b) - b) = (a + b) - a = b, proved.
For all real numbers.
All the buzzt
CornedBee
"Writing specifications is like writing a novel. Writing code is like writing poetry."
- Anonymous, published by Raymond Chen
Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.
-
Nov 28th, 2003, 01:55 PM
#10
Hyperactive Member
why kasracer
my solution should work for any numeric data type
for string
a= "abcd" b ="efg"
memcpy(a+strlen(a),b,strlen(b)) ; a="abcdefg",b="efg"
memcpy(b,a,strlen(a) - strlen(b)) ; a="abcdefg", b="abcd"
memcpy(a,a+strlen(b),strlen(a)-strlen(b)) ; a=a="def",b="abcd"
look i am assuming here that both a and b are big enough... i am not specifically showing here the handling of null term but it is easy to do that
now it looks almost like my last solution
-
Nov 28th, 2003, 03:58 PM
#11
And is completly useless, to be fair. If you want to swap C-style strings, you do
char *t = a;
a = b;
b = t;
Yes, it does cost you an extra variable. But you copy less memory, you only need to change pointer values.
For std::string, you call the swap function.
All the buzzt
CornedBee
"Writing specifications is like writing a novel. Writing code is like writing poetry."
- Anonymous, published by Raymond Chen
Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.
-
Nov 29th, 2003, 06:47 PM
#12
Hyperactive Member
Thats the point CornedBee : we should not use a third variable.
-
Nov 30th, 2003, 04:19 AM
#13
All the buzzt
CornedBee
"Writing specifications is like writing a novel. Writing code is like writing poetry."
- Anonymous, published by Raymond Chen
Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.
-
Nov 30th, 2003, 02:35 PM
#14
Monday Morning Lunatic
I refuse to tie my hands behind my back and hear somebody say "Bend Over, Boy, Because You Have It Coming To You".
-- Linus Torvalds
-
Dec 5th, 2003, 10:50 AM
#15
Hyperactive Member
-
Dec 25th, 2003, 01:41 AM
#16
Frenzied Member
Originally posted by CornedBee
And is completly useless, to be fair. If you want to swap C-style strings, you do
char *t = a;
a = b;
b = t;
Yes, it does cost you an extra variable. But you copy less memory, you only need to change pointer values.
For std::string, you call the swap function.
yeah.. this is the coolest thing ive seen in c++ so far
-
Jun 28th, 2005, 06:44 PM
#17
Junior Member
Re: C/C++ - Interesting swap function
Code:
template <typename T> void Swap(T & obj1,T & obj2)
{
unsigned char * pObj1 = reinterpret_cast<unsigned char *>(&obj1);
unsigned char * pObj2 = reinterpret_cast<unsigned char *>(&obj2);
for (unsigned long x = 0; x < sizeof(T); ++x)
{
pObj1[x] ^= pObj2[x];
pObj2[x] ^= pObj1[x];
pObj1[x] ^= pObj2[x];
}
}
-
Jun 28th, 2005, 07:40 PM
#18
Re: C/C++ - Interesting swap function
This is wrong on so many levels...
All the buzzt
CornedBee
"Writing specifications is like writing a novel. Writing code is like writing poetry."
- Anonymous, published by Raymond Chen
Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.
-
Jun 28th, 2005, 08:29 PM
#19
Junior Member
Re: C/C++ - Interesting swap function
Originally Posted by CornedBee
This is wrong on so many levels...
How so? The function works. And swaps any object with another. The only REASON not to use this is IF your variables of the objects you're swapping have a member that is a pointer to the parent object. In that case you DO NOT want to use this function.
Let's examine my code.
It's a template. The arguments of the function take a reference to an object of type T.
Then, we use the &Obj1 and &Obj2 to get the 'pointer' of the object and cast those to the unsigned char pointers.
Now, via sizeof(T) the sizeof the object is known. So, we swap each byte of the object with the corresponding index in the other array. Now, the objects have been swapped with the EXACT value they were on the other object.
What if you want to swap two objects that have EXPENSIVE copy constructors?
Say that my object stores data in some array, and that array holds objects that themselves are in an array. Which, BTW is common, you have a class that has a vector of objects, which these objects are themselves of a class that has vectors of objects. Ok, now that is ALOT OF COPY CONSTRUCTORS, something I see needlessly to happen.
If I want to *swap* two of the objects, AND keep performance, it would be simple to just 'swap' them.
Last edited by Dynefire; Jun 29th, 2005 at 02:29 AM.
-
Jun 29th, 2005, 05:24 AM
#20
Re: C/C++ - Interesting swap function
I kind of have a problem with a function that allows this:
Code:
class Base {};
class Derived : public Base {};
Base b; Derived d;
swap(b, d);
It's worse if Base has virtual functions: in that case, b has the vptr of d after the swap, meaning that it thinks it's a Derived object, although it isn't and doesn't have enough space for the Derived variables.
This breaks quite horribly, although you mentioned that the function is not applicable in this case:
Code:
class Base {};
class Derived : public virtual Base {};
Base b; Derived d;
swap(b, d);
Note, however, the reason it breaks: in most memory layouts, this will exchange the bytes of b with the bytes of the Derived-sub-object of d, not even the Base-sub-object of d as the first case does.
Then it's wrong on the philosophical level. You don't low-level manipulate the bytes of a class. You just don't.
Finally, and most importantly, it's not useful. It's slower than the compiler-generated bitblast copy constructors for simple classes, because it copies byte by byte, not machine word by machine word as most bitblasters would do. It's potentially dangerous for large classes with complex and slow copy constructors - and if you need to swap these, you should just give them a fast swap function like std::string, std::vector, std::list and all the other big classes have. They can swap safely and quickly. Specialize std::swap on them to call this version, and you have a simple, safe and fast swap call.
All the buzzt
CornedBee
"Writing specifications is like writing a novel. Writing code is like writing poetry."
- Anonymous, published by Raymond Chen
Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.
-
Jun 29th, 2005, 11:08 AM
#21
Junior Member
Re: C/C++ - Interesting swap function
Originally Posted by CornedBee
Specialize std::swap
Probably the best thing to do.
-
Jul 29th, 2005, 03:09 PM
#22
New Member
Re: C/C++ - Interesting swap function
Originally Posted by sw_is_great
there is another way
int a; -- e.g 10
int b; -- e.g 5
a = a+b ; -- a=15,b=5
b = a-b ; -- a=15,b=10
a= a -b ; -- a= 5,b=10
swapped
The above won't work if the integers are large enough to cause an overflow.
-
Feb 28th, 2006, 07:34 AM
#23
Lively Member
Re: C/C++ - Interesting swap function
Could someone explain the XOR thing,how does it work basically?
-
Oct 18th, 2006, 05:16 AM
#24
Re: C/C++ - Interesting swap function
Originally Posted by sid_19840
Could someone explain the XOR thing, how does it work basically?
XOR (eXclusive OR) is a bitwise operation that will only set a particular bit if both the comparative bits are different. Here is an example.
If we perform 6 XOR 9 these we get 15 why? Lets have a look what’s happening at the bits...
6 in binary is 0110.
9 in binary is 1001.
0110
1001
----
1111
All the bits are "turned on" because none of them have the same value, e.g. one is always 1 and the other always 0.
Lets look at another. 22 XOR 30 is 8. Why?
22 in binary is 10110.
30 in binary is 11110.
10110
11110
------
01000
The first, third, forth and fifth bits are all the same, both have the same bit value so they are all turned to 0. So not lets have a look why the code actually works. We'll use 22 and 30 respectively for out function parameters here.
Code:
void swap(int * a, int *b)
{
a = a xor b;
b = b xor a;
a = a xor b;
}
int main()
{
int a = 22, b = 30;
printf("a is %d, b is %d\n", a, b);
swap(a, b);
printf("a is %d, b is %d\n", a, b);
}
Will print the following to a console screen:
a is 22, b is 30
a is 30, b is 22
Looking at the bits... remember 22 == 10110, 30 == 11110.
void swap(int * a, int *b)
{
a = 10110 xor 11110; // a == 01000
b = 11110 xor 01000; // b == 10110
a = 01000 xor 10110; // a == 11110
}
So b is now 22 (10110) and a is now 30 (11110).
Last edited by sciguyryan; Oct 18th, 2006 at 09:54 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|