поменять местами A и B
От: Аноним  
Дата: 05.06.02 17:46
Оценка:
Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?

16.01.03 23:51: Перенесено из 'Алгоритмы'
Re: поменять местами A и B
От: Андрей Тарасевич Беларусь  
Дата: 05.06.02 17:51
Оценка: 3 (1)
Здравствуйте Аноним, Вы писали:

А>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


Старый избитый прикол

a ^= b ^= a ^= b;


Разумеется, работать это будет только для некоторых типов.
Best regards,
Андрей Тарасевич
Re: поменять местами A и B
От: Акул www.kyrs.ru
Дата: 05.06.02 17:56
Оценка: 6 (1)
Здравствуйте Аноним, Вы писали:

А>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


A = A + B;
B = A — B;
A = A — B;

Re[2]: поменять местами A и B
От: Андрей Тарасевич Беларусь  
Дата: 05.06.02 17:56
Оценка: 10 (1) +1
Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Старый избитый прикол


АТ>
АТ>a ^= b ^= a ^= b;
АТ>


АТ>Разумеется, работать это будет только для некоторых типов.


Хотя, если посмотреть на это внимательнее, то становится ясно, что за такое морду бить надо. Две модификации каждой переменно в рамках одного выражения — неопределенное поведение.

Правильнее так

b ^= a; a ^= b; b ^= a;
Best regards,
Андрей Тарасевич
Re: поменять местами A и B
От: PPA Россия http://flylinkdc.blogspot.com/
Дата: 05.06.02 17:58
Оценка:
Здравствуйте Аноним, Вы писали:

А>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


a += b;
b = a — b;
a -= b;
Re[2]: поменять местами A и B
От: Аноним  
Дата: 05.06.02 18:24
Оценка:
Здравствуйте Акул, Вы писали:

А>Здравствуйте Аноним, Вы писали:


А>>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


А>A = A + B;

А>B = A — B;
А>A = A — B;

А> :super:


М-да. Век живи, век учись :)
Re[2]: поменять местами A и B
От: LeonGorbachev Россия  
Дата: 06.06.02 07:59
Оценка:
Здравствуйте Акул, Вы писали:

А>Здравствуйте Аноним, Вы писали:


А>>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


Есть вопрос — давным давно мне показывали такй метод.
Но потом у меня возник вопрос, после которого я на всякий случай перестал использовать
этот метод : при любых ли значениях и типах А и В это будет работать?
Re[3]: поменять местами A и B
От: Аноним  
Дата: 06.06.02 08:16
Оценка:
Здравствуйте LeonGorbachev, Вы писали:

LG>Есть вопрос — давным давно мне показывали такй метод.

LG>Но потом у меня возник вопрос, после которого я на всякий случай перестал использовать
LG>этот метод : при любых ли значениях и типах А и В это будет работать?
Ну во первых для используемых типов должны быть определены операторы + и -, а также оператора преобразования типов :)
Ну и конечно за переполнением (по крайней мере для встроенных типов) нужно смотреть.
Кстати вариант с xor освобождает от забот с переполнением...
Re[4]: поменять местами A и B
От: Акул www.kyrs.ru
Дата: 06.06.02 08:26
Оценка:
Здравствуйте Аноним, Вы писали:

А>Здравствуйте LeonGorbachev, Вы писали:


А>Ну и конечно за переполнением (по крайней мере для встроенных типов) нужно смотреть.

А>Кстати вариант с xor освобождает от забот с переполнением...

вариант с xor будет работать только для целочисленных типов.
Re[5]: поменять местами A и B
От: Аноним  
Дата: 06.06.02 09:17
Оценка:
Здравствуйте Акул, Вы писали:

А>Здравствуйте Аноним, Вы писали:


А>>Здравствуйте LeonGorbachev, Вы писали:


А>>Ну и конечно за переполнением (по крайней мере для встроенных типов) нужно смотреть.

А>>Кстати вариант с xor освобождает от забот с переполнением...

А>вариант с xor будет работать только для целочисленных типов.


Везде есть свои плюсы и минусы...
Re[6]: поменять местами A и B
От: Кодт Россия  
Дата: 06.06.02 16:26
Оценка:
Здравствуйте Аноним, Вы писали:

А>Здравствуйте Акул, Вы писали:


А>>Здравствуйте Аноним, Вы писали:


А>>>Здравствуйте LeonGorbachev, Вы писали:


А>>>Ну и конечно за переполнением (по крайней мере для встроенных типов) нужно смотреть.

А>>>Кстати вариант с xor освобождает от забот с переполнением...

А>>вариант с xor будет работать только для целочисленных типов.


А>Везде есть свои плюсы и минусы...


В группе по сложению по модулю N (то есть, 2^32) на переполнение можно забить, так как сложение-вычитание будет столь же однозначно.
a = a(+)b   a1 = a0+b0-O
b = a(-)b   b1 = a1-b0   = a0+b0-O-b0   = a0-O
a = a(-)b   a2 = a1-b1   = a0+b0-O-a0+O = b0

где (+), (-) - операции сложения по модулю N
O - величина переполнения, принимает значения 0 или N (что эквивалентно 0).


Можно сказать, что XOR — это поразрядное сложение,

С плавающей точкой такой номер может не пройти, в связи с выравниванием порядков (и, как следствие, отбрасыванием разрядов) в процессе вычислений.
Перекуём баги на фичи!
Re[3]: поменять местами A и B
От: VVV Россия  
Дата: 06.06.02 17:47
Оценка:
Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте Андрей Тарасевич, Вы писали:


АТ>>Старый избитый прикол


АТ>>
АТ>>a ^= b ^= a ^= b;
АТ>>


АТ>>Разумеется, работать это будет только для некоторых типов.


АТ>Хотя, если посмотреть на это внимательнее, то становится ясно, что за такое морду бить надо. Две модификации каждой переменно в рамках одного выражения — неопределенное поведение.


АТ>Правильнее так


АТ>
АТ>b ^= a; a ^= b; b ^= a;
АТ>


Разве и в операторе присваивания будет неопределённое поведение??? Разве не говорится, что сначала вычисляется правая часть и затем присваивается левой? Пожалуйста, дайте выдержку из стандарта где такое использование оператора присваивания считается неопределённым.
Re[4]: поменять местами A и B
От: Андрей Тарасевич Беларусь  
Дата: 08.06.02 04:52
Оценка:
Здравствуйте VVV, Вы писали:

АТ>>>Старый избитый прикол


АТ>>>
АТ>>>a ^= b ^= a ^= b;
АТ>>>


АТ>>>Разумеется, работать это будет только для некоторых типов.


АТ>>Хотя, если посмотреть на это внимательнее, то становится ясно, что за такое морду бить надо. Две модификации каждой переменно в рамках одного выражения — неопределенное поведение.


АТ>>Правильнее так


АТ>>
АТ>>b ^= a; a ^= b; b ^= a;
АТ>>


VVV>Разве и в операторе присваивания будет неопределённое поведение??? Разве не говорится, что сначала вычисляется правая часть и затем присваивается левой? Пожалуйста, дайте выдержку из стандарта где такое использование оператора присваивания считается неопределённым.


Любое выражениие, в котором одна и таже переменная встроенного типа модифицируется более одного раза между парой соседних точек следования, порождает неопределенное поведение. См. пункт 5/4 стандарта языка C++. А какой там оператор значения не имеет. Мой первый вариант страдал именно это проблемой.
Best regards,
Андрей Тарасевич
Re[7]: поменять местами A и B
От: WolfHound  
Дата: 08.06.02 19:50
Оценка:
Здравствуйте Кодт, Вы писали:

К>В группе по сложению по модулю N (то есть, 2^32) на переполнение можно забить, так как сложение-вычитание будет столь же однозначно.

К>
К>a = a(+)b   a1 = a0+b0-O
К>b = a(-)b   b1 = a1-b0   = a0+b0-O-b0   = a0-O
К>a = a(-)b   a2 = a1-b1   = a0+b0-O-a0+O = b0

К>где (+), (-) - операции сложения по модулю N
К>O - величина переполнения, принимает значения 0 или N (что эквивалентно 0).
К>


К>Можно сказать, что XOR — это поразрядное сложение,


К>С плавающей точкой такой номер может не пройти, в связи с выравниванием порядков (и, как следствие, отбрасыванием разрядов) в процессе вычислений.

Хм а чем 4 байта float отличаются от 4-х байт int?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: поменять местами A и B
От: Кодт Россия  
Дата: 10.06.02 09:46
Оценка: 6 (1) +1
Здравствуйте WolfHound, Вы писали:

К>>С плавающей точкой такой номер может не пройти, в связи с выравниванием порядков (и, как следствие, отбрасыванием разрядов) в процессе вычислений.


WH>Хм а чем 4 байта float отличаются от 4-х байт int? :???:


Как это чем? Форматом, смыслом, правилами использования.

При суммировании/вычитании двух чисел с плавающей запятой
1) Нормализуются порядки (приводятся к наибольшему), при этом мантисса числа с меньшим порядком сдвигается (делится) на разность порядков. Отбрасываются младшие разряды, происходит потеря данных.
2) Мантиссы складываются/вычитаются, при этом если возникло переполнение, то порядок инкрементируется на 1, а мантисса суммы сдвигается (делится) на 1 порядок. Еще один разряд теряется.
3) Мантисса суммы нормализуется: если старшие разряды = 0, то порядок декрементируется, а мантисса сдвигается (умножается), при этом младшие разряды заполняются значением исходного младшего разряда.

Таким образом, привносятся 3 ошибки: денормализации, переполнения и нормализации.
Поскольку разрядность ограничена форматом числа (4 байта), то эти ошибки не компенсируются.

Если хочется обменять любые 4-байтные данные с помощью сложения-вычитания, то извольте:
template <class T>
inline void swap_integer(T& a, T& b)
{
  a += b;
  b = a-b;
  a -= b;
}

template <class T>
inline void swap_dword(T& a, T& b)
{
  assert(sizeof(T)) == 4;
  swap_integer(*(long*)(void*)(&a), *(long*)(void*)(&b));
}

template <class T>
inline void swap_qword(T& a, T& b)
{
  assert(sizeof(T)) == 8;
  swap_integer(*(long long*)(void*)(&a), *(long long*)(void*)(&b));
}

// специализации для вещественных чисел
// используют обобщенный механизм (а не целочисленный)
inline void swap_integer(float& a, float& b)
{
  swap_dword(a, b);
}

inline void swap_integer(double& a, double& b)
{
  swap_qword(a, b);
}


А вообще это все баловство.
Перекуём баги на фичи!
Re[5]: поменять местами A и B
От: VVV Россия  
Дата: 10.06.02 10:32
Оценка:
Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Здравствуйте VVV, Вы писали:


АТ>>>>Старый избитый прикол


АТ>>>>
АТ>>>>a ^= b ^= a ^= b;
АТ>>>>


АТ>>>>Разумеется, работать это будет только для некоторых типов.


АТ>>>Хотя, если посмотреть на это внимательнее, то становится ясно, что за такое морду бить надо. Две модификации каждой переменно в рамках одного выражения — неопределенное поведение.


АТ>>>Правильнее так


АТ>>>
АТ>>>b ^= a; a ^= b; b ^= a;
АТ>>>


VVV>>Разве и в операторе присваивания будет неопределённое поведение??? Разве не говорится, что сначала вычисляется правая часть и затем присваивается левой? Пожалуйста, дайте выдержку из стандарта где такое использование оператора присваивания считается неопределённым.


АТ>Любое выражениие, в котором одна и таже переменная встроенного типа модифицируется более одного раза между парой соседних точек следования, порождает неопределенное поведение. См. пункт 5/4 стандарта языка C++. А какой там оператор значения не имеет. Мой первый вариант страдал именно это проблемой.


Т.е. нижеследующая строка приводит к неопределённому поведению?

a=b=a=b=a=b=1;

(просто хочу, чтобы ты сам понял, что нет здесь никакого неопределённого поведения, что значение (результат) оператора присваивания (не рассматриваем переопределённое присваивание) есть результат выражения правой части (приведённый, конечно, к типу переменной слева)).

и в выражении a ^= b ^= a ^= b; операторы присваивания будут выполняться справа налево (в соответствии со стандартом) с полностью определённым поведением.
Re: поменять местами A и B
От: sadomovalex Россия http://sadomovalex.blogspot.com
Дата: 08.10.04 12:19
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


как вам такой способ:

double x1 = 1.1, x2 = 2.5;

double foo(double &a)
{
    __try {
        return a;
    }
    __finally
    {
        a = x1;
    }
}

x1 = foo(x2);
"Что не завершено, не сделано вовсе" Гаусс
Re[9]: поменять местами A и B
От: PVA  
Дата: 08.10.04 14:20
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Если хочется обменять любые 4-байтные данные с помощью сложения-вычитания, то извольте:

К>...
К>А вообще это все баловство.

Как всегда, в самый глубь заглянул

typedef unsigned char BYTE, *PBYTE;

inline void swap_bytes(BYTE &a, BYTE &b)
{
 b ^= a; a ^= b; b ^= a;
}

template<typename A>
void swap(A &a, A &b)
{
 PBYTE pa = reinterpret_cast<PBYTE>(&a);
 PBYTE pb = reinterpret_cast<PBYTE>(&b);

 for(int i = 0; i < sizeof(A); ++i)
  swap_bytes(pa[i], pb[i]);
}


Только не ногами
newbie
Re[2]: поменять местами A и B
От: PVA  
Дата: 08.10.04 14:24
Оценка:
Здравствуйте, sadomovalex, Вы писали:

S>
S>double x1 = 1.1, x2 = 2.5;

S>double foo(double &a)
S>{
S>    __try {
S>        return a;
S>    }
S>    __finally
S>    {
S>        a = x1;
S>    }
S>}

S>x1 = foo(x2);
S>


И помимо всего прочего здесь третьей переменной выступает стек.
newbie
Re[2]: поменять местами A и B
От: Socrat Россия  
Дата: 11.10.04 09:47
Оценка:
Здравствуйте, sadomovalex, Вы писали:

S>Здравствуйте, Аноним, Вы писали:


А>>Привет. Что за приколы такие, есть два числа A и B, надо поменять значения А и B местами без использования дополнительной ячейки памяти. Я так полагаю, что это невозможно. Есть какие-нить мнения?


S>как вам такой способ:


[skip]

А такой:

($a,$b) = ($b,$a)
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.