how can we swap pointers with out using a temporary variable
Printable View
how can we swap pointers with out using a temporary variable
Since addresses are integers you could use the XOR swap trick, but don't bother: just use a temporary variable.
can we use bitwise operators on float variables
float x, y;
float temp = x;
x = y;
y = temp;
Just change accordingly to your code. It's the simple swap algorithm.
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
XCHG instruction has be available from 8086(intel). all x86 and above architectures have it as a part of their instruction set.
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?
source code
assembly instruction by gcc inline assemblerCode:#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);
}
optimised (O3)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
xchg is not called after all(making compiler call xchg/swp isnt easy after all)...and when optimised, both are exactly the same.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
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'.
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.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
--
Mats
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
This is called optimization:
And assembly (phew, finally real asm, instead of that bloody gcc mess):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);
}
The compiler is pretty clever.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
To force the compiler to execute the swap, let's read some numbers and see what it does:
And assembly: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);
}
(Interesting part bolded.)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
To separate the two functions calls apart to see what it does, we use a slightly different code:
And the assembly: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);
}
Again, the interesting parts bolded.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
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.