замена двух целых чисел без создания третьего переполнения

Question

Я пытаюсь написать функцию подкачки без использования tmp в C, вот что я использую:

void swap(int *a, int* b) {
    *a += *b;
    *b = *a - *b;
    *a -= *b;
}

Теперь одна проблема (или я так думал) с этим заключается в том, что мы можем переполниться, если *a + * b > INT_MAX. Что сбивает с толку, так это то, что на самом деле это работает просто отлично, даже с крайними случаями .. может кто-нибудь объяснить, почему ??

Вот несколько тестов, которые я использовал:

int main() {
    int t1Swap[] = {INT_MAX, 1};
    int t2Swap[] = {INT_MAX, INT_MIN};
    int t3Swap[] = {INT_MAX, INT_MAX-1000};
    int t4Swap[] = {INT_MIN, INT_MIN+1000};
}

Заранее спасибо!

Answer 1

, если вы стремитесь как можно быстрее сгенерировать код (или сэкономить память), сложные методы XOR или add - не лучший выбор:

Рассмотрим:

void swap1(int *a, int *b)
{
    *a=*a^*b;
    *b=*a^*b;
    *a=*a^*b;
}

void swap2(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

и результирующий код: X86

swap1:
        mov     eax, DWORD PTR [rdi]
        xor     eax, DWORD PTR [rsi]
        mov     DWORD PTR [rdi], eax
        xor     eax, DWORD PTR [rsi]
        mov     DWORD PTR [rsi], eax
        xor     DWORD PTR [rdi], eax
        ret
swap2:
        mov     eax, DWORD PTR [rdi]
        mov     edx, DWORD PTR [rsi]
        mov     DWORD PTR [rdi], edx
        mov     DWORD PTR [rsi], eax
        ret

Таким образом, без временной переменной вы не экономите память, а замедляете алгоритм.Какой смысл?

Answer 2

Переполнение со знаком целого числа является неопределенным поведением, поэтому оно может или не может работать в зависимости от вашей конкретной системы и компилятора. Чтобы избежать этого неопределенного поведения, используйте побитовый оператор XOR вместо сложения и вычитания для замены переменных без введения temp:

a=a^b;
b=a^b;
a=a^b;

Answer 3

Хотя целочисленное переполнение является технически неопределенным поведением, оно обычно переносится в INT_MIN.В этом случае ваша арифметическая реализация работает (но она не переносима).

Answer 4

Вы можете использовать XOR, как это;

void swap(int *a, int *b)
{
    if (*a != *b)
    {
        *a^=*b;
        *b^=*a;
        *a^=*b;
    }
}