Thread: swapping pointers

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    14

    Unhappy swapping pointers

    how can we swap pointers with out using a temporary variable

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Since addresses are integers you could use the XOR swap trick, but don't bother: just use a temporary variable.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    14
    can we use bitwise operators on float variables

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    float x, y;
    float temp = x;
    x = y;
    y = temp;
    Just change accordingly to your code. It's the simple swap algorithm.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by csvraju View Post
    can we use bitwise operators on float variables
    Not directly, no. You would have to store the value in memory, take it's address, and then perform the xor on the stored value. This certainly more code and takes longer to execute than the corresponding swap operation.

    The "don't use a temporary" is of no real meaning these days. It was "clever" at the time when processors only had 3 registers.

    If you really want to be clever with it, find out if the processor has a swap/exchange instruction, and use that. But that's not very portable.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    apprentiCe
    Join Date
    Oct 2008
    Location
    Hyderabad,India
    Posts
    136
    XCHG instruction has be available from 8086(intel). all x86 and above architectures have it as a part of their instruction set.
    Code:
    printf("%c%c%c%c%c%c%c",0x68,0x68^0xd,0x68|0x4,0x68|0x4,0x68|0xf,0x68^0x49,0x68^0x62);

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by creeping death View Post
    XCHG instruction has be available from 8086(intel) all x86 and above architectures have it as a part of their instruction set.
    Sure, and other processors often have the same thing. It's a case of "how to get the compiler to generate it", however.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    apprentiCe
    Join Date
    Oct 2008
    Location
    Hyderabad,India
    Posts
    136
    yes,and although i dont know much about code optimisation, but i have heard that there are more chances, the compiler would recognise that the user is trying to swap(and use XCHG) by use of a temp variable that by the XOR method or any of their variations. isnt that right?
    Code:
    printf("%c%c%c%c%c%c%c",0x68,0x68^0xd,0x68|0x4,0x68|0x4,0x68|0xf,0x68^0x49,0x68^0x62);

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by creeping death View Post
    yes,and although i dont know much about code optimisation, but i have heard that there are more chances, the compiler would recognise that the user is trying to swap(and use XCHG) by use of a temp variable that by the XOR method or any of their variations. isnt that right?
    It is MUCH easier for a compiler to realize that
    Code:
    temp = a;
    a = b;
    b = temp;
    is a swap than it is to detect the xor pattern is a swap - but sure, the optimizer could be written to recognize both/either one.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    DESTINY BEN10's Avatar
    Join Date
    Jul 2008
    Location
    in front of my computer
    Posts
    804
    Quote Originally Posted by csvraju View Post
    can we use bitwise operators on float variables
    you can use them for int and also char but not for float and double.

  11. #11
    apprentiCe
    Join Date
    Oct 2008
    Location
    Hyderabad,India
    Posts
    136
    Quote Originally Posted by matsp View Post
    It is MUCH easier for a compiler to realize that
    Code:
    temp = a;
    a = b;
    b = temp;
    is a swap than it is to detect the xor pattern is a swap - but sure, the optimizer could be written to recognize both/either one.

    --
    Mats
    source code
    Code:
    #include<stdio.h>
    
    void swap(int x,int y)
    {
        int temp;
        temp=x;
        x=y;
        y=temp;
    }
    
    void swap2(int x,int y)
    {
        x=x^y;
        y=x^y;
        x=x^y;
    }
    
    int main()
    {
        int x=3,y=4;
        swap(x,y);
        swap2(x,y);
        printf("x=%d,y=%d",x,y);
    }
    assembly instruction by gcc inline assembler
    Code:
    swap:
    	pushl	%ebp
    	movl	%esp, %ebp
    	subl	$16, %esp
    	movl	8(%ebp), %eax
    	movl	%eax, -4(%ebp)
    	movl	12(%ebp), %eax
    	movl	%eax, 8(%ebp)
    	movl	-4(%ebp), %eax
    	movl	%eax, 12(%ebp)
    	leave
    	ret
    	.size	swap, .-swap
    .globl swap2
    	.type	swap2, @function
    swap2:
    	pushl	%ebp
    	movl	%esp, %ebp
    	movl	12(%ebp), %eax
    	xorl	%eax, 8(%ebp)
    	movl	8(%ebp), %eax
    	xorl	%eax, 12(%ebp)
    	movl	12(%ebp), %eax
    	xorl	%eax, 8(%ebp)
    	popl	%ebp
    	ret
    	.size	swap2, .-swap2
    	.section	.rodata
    optimised (O3)
    Code:
    swap:
    	pushl	%ebp
    	movl	%esp, %ebp
    	popl	%ebp
    	ret
    	.size	swap, .-swap
    .globl swap2
    	.type	swap2, @function
    swap2:
    	pushl	%ebp
    	movl	%esp, %ebp
    	popl	%ebp
    	ret
    	.size	swap2, .-swap2
    	.section	.rodata.str1.1,"aMS",@progbits,1
    xchg is not called after all(making compiler call xchg/swp isnt easy after all)...and when optimised, both are exactly the same.
    Last edited by creeping death; 03-31-2009 at 07:12 AM.
    Code:
    printf("%c%c%c%c%c%c%c",0x68,0x68^0xd,0x68|0x4,0x68|0x4,0x68|0xf,0x68^0x49,0x68^0x62);

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Actually, the compiler optimized away ALL of the swap function, since all it does is change the local copies of x and y. You didn't actually test your code, did you?

    I will be back with proper code.

    I do not expect the compiler to generate the xchg instruction tho'.

    Code:
    _swap:
    	pushl	%ebp
    	movl	%esp, %ebp
    	movl	8(%ebp), %edx
    	pushl	%ebx
    	movl	12(%ebp), %ecx
    	movl	(%edx), %ebx
    	movl	(%ecx), %eax
    	movl	%eax, (%edx)
    	movl	%ebx, (%ecx)
    	popl	%ebx
    	popl	%ebp
    	ret
    	.p2align 4,,15
    .globl _swap2
    	.def	_swap2;	.scl	2;	.type	32;	.endef
    _swap2:
    	pushl	%ebp
    	movl	%esp, %ebp
    	movl	12(%ebp), %edx
    	movl	8(%ebp), %ecx
    	movl	(%edx), %eax
    	xorl	(%ecx), %eax
    	movl	%eax, (%ecx)
    	xorl	(%edx), %eax
    	movl	%eax, (%edx)
    	xorl	%eax, (%ecx)
    	popl	%ebp
    	ret
    ...
    _main:
    	pushl	%ebp
    	movl	$16, %eax
    	movl	%esp, %ebp
    	subl	$24, %esp
    	andl	$-16, %esp
    	call	__alloca
    	call	___main
    	movl	$LC0, (%esp)
    	movl	$4, %ecx
    	movl	$3, %eax
    	movl	%ecx, 4(%esp)
    	movl	%eax, 8(%esp)
    	call	_printf
    	movl	$LC0, (%esp)
    	movl	$4, %edx
    	movl	$3, %eax
    	movl	%edx, 8(%esp)
    	movl	%eax, 4(%esp)
    	call	_printf
    	leave
    	xorl	%eax, %eax
    	ret
    Note that it actualy inlines the entire swap and does it without even calling swap in this case. I'll see if I can come up with a more complex case where it does call swap.

    --
    Mats
    Last edited by matsp; 03-31-2009 at 07:16 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    apprentiCe
    Join Date
    Oct 2008
    Location
    Hyderabad,India
    Posts
    136
    Quote Originally Posted by matsp View Post
    Actually, the compiler optimized away ALL of the swap function, since all it does is change the local copies of x and y. You didn't actually test your code, did you?

    I will be back with proper code.

    I do not expect the compiler to generate the xchg instruction tho'.

    --
    Mats
    i see..and no
    Last edited by creeping death; 03-31-2009 at 07:17 AM.
    Code:
    printf("%c%c%c%c%c%c%c",0x68,0x68^0xd,0x68|0x4,0x68|0x4,0x68|0xf,0x68^0x49,0x68^0x62);

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Further to my edit above:
    1. It seems like (at least in trivial cases) the compiler at least understands that the point of the XOR swap is to swap elements [or at least that this is the effect of it].
    2. It's pretty hard to get gcc -O3 to actually CALL the function swap - it just swaps the variables inline.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    This is called optimization:
    Code:
    #include <stdio.h>
    
    void swap(int* x, int* y)
    {
        int temp = *x;
        *x = *y;
        *y = temp;
    }
    
    void swap2(int* x, int* y)
    {
        *x ^= *y;
        *y = *x ^ *y;
        *x ^= *y;
    }
    
    int main()
    {
        int x = 3, y = 4;
    	int z = 4, w = 3;
        swap(&x, &y);
        swap2(&z, &w);
        printf("x = %d, y = %d\n", x, y);
        printf("z = %d, w = %d\n", z, w);
    }
    And assembly (phew, finally real asm, instead of that bloody gcc mess):
    Code:
    int main()
    {
    00951000  push        esi  
        int x = 3, y = 4;
    	int z = 4, w = 3;
        swap(&x, &y);
        swap2(&z, &w);
        printf("x = %d, y = %d\n", x, y);
    00951001  mov         esi,dword ptr [__imp__printf (9520A0h)] 
    00951007  push        3    
    00951009  push        4    
    0095100B  push        offset ___xi_z+34h (9520F4h) 
    00951010  call        esi  
        printf("z = %d, w = %d\n", z, w);
    00951012  push        4    
    00951014  push        3    
    00951016  push        offset ___xi_z+44h (952104h) 
    0095101B  call        esi  
    0095101D  add         esp,18h 
    }
    00951020  xor         eax,eax 
    00951022  pop         esi  
    00951023  ret
    The compiler is pretty clever.

    To force the compiler to execute the swap, let's read some numbers and see what it does:
    Code:
    #include <stdio.h>
    
    void swap(int* x, int* y)
    {
        int temp = *x;
        *x = *y;
        *y = temp;
    }
    
    void swap2(int* x, int* y)
    {
        *x ^= *y;
        *y = *x ^ *y;
        *x ^= *y;
    }
    
    int main()
    {
        int x = 3, y = 4;
    	int z = 4, w = 3;
    	printf("Enter 4 integers: ");
    	scanf("%d %d %d %d", &x, &y, &z, &w);
        swap(&x, &y);
        swap2(&z, &w);
        printf("x = %d, y = %d\n", x, y);
        printf("z = %d, w = %d\n", z, w);
    }
    And assembly:
    Code:
    int main()
    {
    00881000  sub         esp,10h 
    00881003  push        esi  
        int x = 3, y = 4;
    	int z = 4, w = 3;
    	printf("Enter 4 integers: ");
    00881004  mov         esi,dword ptr [__imp__printf (88209Ch)] 
    0088100A  mov         ecx,3 
    0088100F  mov         eax,4 
    00881014  push        edi  
    00881015  push        offset ___xi_z+30h (8820F4h) 
    0088101A  mov         dword ptr [esp+14h],ecx 
    0088101E  mov         dword ptr [esp+18h],eax 
    00881022  mov         dword ptr [esp+10h],eax 
    00881026  mov         dword ptr [esp+0Ch],ecx 
    0088102A  call        esi  
    	scanf("%d %d %d %d", &x, &y, &z, &w);
    0088102C  lea         eax,[esp+0Ch] 
    00881030  push        eax  
    00881031  lea         ecx,[esp+14h] 
    00881035  push        ecx  
    00881036  lea         edx,[esp+20h] 
    0088103A  push        edx  
    0088103B  lea         eax,[esp+20h] 
    0088103F  push        eax  
    00881040  push        offset ___xi_z+44h (882108h) 
    00881045  call        dword ptr [__imp__scanf (8820A4h)] 
        swap(&x, &y);
        swap2(&z, &w);
    0088104B  mov         edx,dword ptr [esp+20h] 
    0088104F  mov         eax,dword ptr [esp+28h] 
    00881053  mov         ecx,dword ptr [esp+24h] 
    00881057  mov         edi,dword ptr [esp+2Ch] 
    0088105B  xor         ecx,edx 
        printf("x = %d, y = %d\n", x, y);
    0088105D  push        eax  
    0088105E  xor         edx,ecx 
    00881060  xor         ecx,edx 
    00881062  push        edi  
    00881063  push        offset ___xi_z+50h (882114h) 
    00881068  mov         dword ptr [esp+34h],edi 
    0088106C  mov         dword ptr [esp+38h],eax 
    00881070  mov         dword ptr [esp+2Ch],edx 
    00881074  mov         dword ptr [esp+30h],ecx 
    00881078  call        esi  
        printf("z = %d, w = %d\n", z, w);
    0088107A  mov         ecx,dword ptr [esp+2Ch] 
    0088107E  mov         edx,dword ptr [esp+30h] 
    00881082  push        ecx  
    00881083  push        edx  
    00881084  push        offset ___xi_z+60h (882124h) 
    00881089  call        esi  
    0088108B  add         esp,30h 
    0088108E  pop         edi  
    }
    0088108F  xor         eax,eax 
    00881091  pop         esi  
    00881092  add         esp,10h 
    00881095  ret
    (Interesting part bolded.)

    To separate the two functions calls apart to see what it does, we use a slightly different code:
    Code:
    #include <stdio.h>
    
    void swap(int* x, int* y)
    {
        int temp = *x;
        *x = *y;
        *y = temp;
    }
    
    void swap2(int* x, int* y)
    {
        *x ^= *y;
        *y = *x ^ *y;
        *x ^= *y;
    }
    
    int main()
    {
        int x = 3, y = 4;
    	int z = 4, w = 3;
    	printf("Enter 4 integers: ");
    	scanf("%d %d %d %d", &x, &y, &z, &w);
        swap(&x, &y);
        printf("x = %d, y = %d\n", x, y);
        swap2(&z, &w);
        printf("z = %d, w = %d\n", z, w);
    }
    And the assembly:
    Code:
    int main()
    {
    00031000  sub         esp,10h 
    00031003  push        esi  
        int x = 3, y = 4;
    	int z = 4, w = 3;
    	printf("Enter 4 integers: ");
    00031004  mov         esi,dword ptr [__imp__printf (3209Ch)] 
    0003100A  mov         ecx,3 
    0003100F  mov         eax,4 
    00031014  push        offset ___xi_z+30h (320F4h) 
    00031019  mov         dword ptr [esp+8],ecx 
    0003101D  mov         dword ptr [esp+0Ch],eax 
    00031021  mov         dword ptr [esp+14h],eax 
    00031025  mov         dword ptr [esp+10h],ecx 
    00031029  call        esi  
    	scanf("%d %d %d %d", &x, &y, &z, &w);
    0003102B  lea         eax,[esp+10h] 
    0003102F  push        eax  
    00031030  lea         ecx,[esp+18h] 
    00031034  push        ecx  
    00031035  lea         edx,[esp+14h] 
    00031039  push        edx  
    0003103A  lea         eax,[esp+14h] 
    0003103E  push        eax  
    0003103F  push        offset ___xi_z+44h (32108h) 
    00031044  call        dword ptr [__imp__scanf (320A4h)] 
        swap(&x, &y);
    0003104A  mov         eax,dword ptr [esp+1Ch] 
    0003104E  mov         ecx,dword ptr [esp+20h] 
        printf("x = %d, y = %d\n", x, y);
    00031052  push        eax  
    00031053  push        ecx  
    00031054  push        offset ___xi_z+50h (32114h) 
    00031059  mov         dword ptr [esp+28h],ecx 
    0003105D  mov         dword ptr [esp+2Ch],eax 
    00031061  call        esi  
        swap2(&z, &w);
    00031063  mov         ecx,dword ptr [esp+30h] 
    00031067  mov         eax,dword ptr [esp+34h] 
    0003106B  xor         eax,ecx 
    0003106D  xor         ecx,eax 
    0003106F  xor         eax,ecx 
        printf("z = %d, w = %d\n", z, w);
    00031071  push        ecx  
    00031072  push        eax  
    00031073  push        offset ___xi_z+60h (32124h) 
    00031078  mov         dword ptr [esp+3Ch],ecx 
    0003107C  mov         dword ptr [esp+40h],eax 
    00031080  call        esi  
    00031082  add         esp,30h 
    }
    00031085  xor         eax,eax 
    00031087  pop         esi  
    00031088  add         esp,10h 
    0003108B  ret
    Again, the interesting parts bolded.
    Actually, as we see, the compiler actually created somewhat more efficient code for the first swap, I'd say.

    This was using Visual Studio 2008 (compiled as C++ with all optimizations enabled).
    Hope this gives some interesting data.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Swapping pointers
    By Mostly Harmless in forum C++ Programming
    Replies: 6
    Last Post: 11-30-2008, 11:07 PM
  2. Swapping Pointers & Arrays
    By bartybasher in forum C++ Programming
    Replies: 6
    Last Post: 10-25-2003, 02:17 PM
  3. Swapping string char with pointers
    By Black-Hearted in forum C++ Programming
    Replies: 4
    Last Post: 06-18-2003, 05:36 AM
  4. Staticly Bound Member Function Pointers
    By Polymorphic OOP in forum C++ Programming
    Replies: 29
    Last Post: 11-28-2002, 01:18 PM