交換指針值

Question

如何在不使用臨時變量的情況下交換兩個指針的值。通過交換值我指的是存儲在每個指針中的地址。指針可以是任何類型，如int。這是高通的面試問題。據我所知，只有指針才允許減法，我們不能執行任何其他的算術運算。

Answer 1

這是一個解決方案，適用於amd64（又名x86_64）或任何其他64位系統，其中高16位地址位未使用（此要求未在代碼中檢查！）。

#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'; 
} 

關於高16個地址位作爲可用作高速暫存序號：Using the extra 16 bits in 64-bit pointers

如果您想了解對於上述生成的彙編代碼：

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 

對戰使用std::swap() ：

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

所以是的，太可怕了。

編輯：這是一個被@阿杰的回答生成的彙編：

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 

相比std::swap()，它花費兩個額外的指令並保存一個寄存器（rdx）。

Answer 2

這種簡單的方法將工作，照顧類型轉換。在我的機器中，它的指針大小等於很長。

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