C/C++ - Interesting swap function-VBForums
Results 1 to 24 of 24

Thread: C/C++ - Interesting swap function

Hybrid View

  1. #1

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    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;
    }
    Code Ronin

  2. #2
    PowerPoster
    Join Date
    Feb 2002
    Location
    Canada, Toronto
    Posts
    5,716
    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; 
    }

  3. #3

    Thread Starter
    Addicted Member CodeRonin's Avatar
    Join Date
    Jul 2002
    Location
    Vienna, Austria
    Posts
    233

    Yeah

    Sorry, forgot it
    Code Ronin

  4. #4
    Lively Member neodatatype's Avatar
    Join Date
    Aug 2002
    Location
    Italy
    Posts
    103

    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.
    > NeoDataType.net <

    Try my Free .Net Reporting Tool!

  5. #5
    Monday Morning Lunatic parksie's Avatar
    Join Date
    Mar 2000
    Location
    Mashin' on the motorway
    Posts
    8,169
    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

  6. #6
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    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.

  7. #7
    Hyperactive Member sw_is_great's Avatar
    Join Date
    Nov 2003
    Posts
    330
    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
    Regards

  8. #8
    New Member
    Join Date
    Jul 2005
    Posts
    1

    Re: C/C++ - Interesting swap function

    Quote 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.

  9. #9
    KrisSiegel.com Kasracer's Avatar
    Join Date
    Jul 2003
    Location
    USA, Maryland
    Posts
    4,981
    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.

  10. #10
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    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.

  11. #11
    Hyperactive Member sw_is_great's Avatar
    Join Date
    Nov 2003
    Posts
    330
    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
    Regards

  12. #12
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    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.

  13. #13
    Hyperactive Member sw_is_great's Avatar
    Join Date
    Nov 2003
    Posts
    330
    Thats the point CornedBee : we should not use a third variable.
    Regards

  14. #14
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594
    Bah.
    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.

  15. #15
    Monday Morning Lunatic parksie's Avatar
    Join Date
    Mar 2000
    Location
    Mashin' on the motorway
    Posts
    8,169
    Seconded.
    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

  16. #16
    Hyperactive Member sw_is_great's Avatar
    Join Date
    Nov 2003
    Posts
    330
    Regards

  17. #17
    Frenzied Member dis1411's Avatar
    Join Date
    Mar 2001
    Posts
    1,048
    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

  18. #18
    Junior Member
    Join Date
    Jun 2005
    Posts
    16

    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];
        }
    }

  19. #19
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    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.

  20. #20
    Junior Member
    Join Date
    Jun 2005
    Posts
    16

    Re: C/C++ - Interesting swap function

    Quote 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.

  21. #21
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    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.

  22. #22
    Junior Member
    Join Date
    Jun 2005
    Posts
    16

    Re: C/C++ - Interesting swap function

    Quote Originally Posted by CornedBee
    Specialize std::swap
    Probably the best thing to do.

  23. #23
    Lively Member
    Join Date
    Dec 2005
    Posts
    68

    Re: C/C++ - Interesting swap function

    Could someone explain the XOR thing,how does it work basically?

  24. #24
    Frenzied Member sciguyryan's Avatar
    Join Date
    Sep 2003
    Location
    Wales
    Posts
    1,763

    Re: C/C++ - Interesting swap function

    Quote 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.
    My Blog.

    Ryan Jones.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width

Survey posted by VBForums.