Swap Pointer values

Question

How to swap values of two pointers without using a temporary variable. By swapping values I mean the address which is stored in each pointer. Pointer can be of any type say int. This is an interview question of Qualcomm. As per my knowledge, only subtraction is allowed with pointers, we cannot perform any other arithmetic operation.

Answer 1

Here is a solution that works on amd64 (aka x86_64), or any other 64-bit system where the high 16 address bits are unused (this requirement is not checked in the code!).

#include <cassert>
#include <cstring>
#include <iostream>

// swap two pointers without using any additional space
// this is really a terrible idea and should never be used
template <typename T>
void ptr_swap(T*& p1, T*& p2)
{
    // this only works on amd64, where the high 16 address bits are unused
    static_assert(sizeof(T*) == 8, "only works on amd64");

// swap Nth pair of bytes
#define PTR_SWAP_PAIR(N) \
    memcpy((char*)&p1 + 6, (char*)&p2 + N, 2); \
    memcpy((char*)&p2 + N, (char*)&p1 + N, 2); \
    memcpy((char*)&p1 + N, (char*)&p1 + 6, 2); \

    PTR_SWAP_PAIR(0);
    PTR_SWAP_PAIR(2);
    PTR_SWAP_PAIR(4);

    // restore amd64 pointer invariant (sign extension)
    p1 = (T*)(((intptr_t)p1 << 16) >> 16);
}

int main()
{
    int a = 1234567890;
    int b = 999777555;
    int* pa = &a;
    int* pb = &b;

    ptr_swap(pa, pb);

    assert(pa == &b);
    assert(pb == &a);

    std::cout << *pa << '\n';
    std::cout << *pb << '\n';
}

Reference regarding the high 16 address bits being usable as a scratch pad: Using the extra 16 bits in 64-bit pointers

If you're curious about the assembly code generated for the above:

    movzx   eax, WORD PTR [rsi]
    mov     WORD PTR [rdi+6], ax
    movzx   eax, WORD PTR [rdi]
    mov     WORD PTR [rsi], ax
    movzx   eax, WORD PTR [rdi+6]
    mov     WORD PTR [rdi], ax
    movzx   eax, WORD PTR [rsi+2]
    mov     WORD PTR [rdi+6], ax
    movzx   eax, WORD PTR [rdi+2]
    mov     WORD PTR [rsi+2], ax
    movzx   eax, WORD PTR [rdi+6]
    mov     WORD PTR [rdi+2], ax
    movzx   eax, WORD PTR [rsi+4]
    mov     WORD PTR [rdi+6], ax
    movzx   eax, WORD PTR [rdi+4]
    mov     WORD PTR [rsi+4], ax
    movzx   eax, WORD PTR [rdi+6]
    mov     WORD PTR [rdi+4], ax
    mov     eax, 16
    shlx    rax, QWORD PTR [rdi], rax
    sar     rax, 16
    mov     QWORD PTR [rdi], rax

Versus using std::swap():

    mov     rax, QWORD PTR [rdi]
    mov     rdx, QWORD PTR [rsi]
    mov     QWORD PTR [rdi], rdx
    mov     QWORD PTR [rsi], rax

So yeah, horrible.

Edit: Here's the assembly generated by @Ajay's answer:

    mov     rax, QWORD PTR [rdi]
    xor     rax, QWORD PTR [rsi]
    mov     QWORD PTR [rdi], rax
    xor     rax, QWORD PTR [rsi]
    mov     QWORD PTR [rsi], rax
    xor     QWORD PTR [rdi], rax

Compared to std::swap(), it spends two extra instructions and saves one register (rdx).

Answer 2

This simple way will work, take care of typecasting. In my machine its pointer size equals to long.

#include <stdio.h>
int main()
{
    int *x = malloc(sizeof(int)), *y = malloc(sizeof(int));

    printf("Before Swap x: %p y: %p \n", x, y);

    // if x= 5 & y = 10, 
    // then code to swap 'x' (1010) and 'y' (0101)
    x = (int*)((uintptr_t )x ^ (uintptr_t )y); // x = x ^ y, now x becomes 15 (1111)
    y = (int*)((uintptr_t )x ^ (uintptr_t )y); // y = x ^ y, y becomes 10 (1010)
    x = (int*)((uintptr_t )x ^ (uintptr_t )y); // x = X ^ y, x becomes 5 (0101)

    printf("After Swapping: x = %p, y = %p", x, y);

    return 0;
}