Поменять два числа в памяти

Что-то в стиле:

a = a - b;
b = b + a;
a = b - a;

Настоящие пацаны делают через xor

А если переполнение?

xchg reg, mem

Например?

int main()
{
	unsigned int a = 10, b = 20;
	std::cout << "a = " << a << "; b = " << b << '\n';	

	a = a - b;
	b = b + a;
	a = b - a;

	std::cout << "a = " << a << "; b = " << b << '\n';
	
	return 0;
}

a = 10; b = 20
a = 20; b = 10

Какой простор для «всем переругаться».

про атомарность забыл :)

А теперь поменяй местами 2**31 + 1 и 2**31 + 2.

Для беззнаковых «проворачиваемость» определена, если я не ошибаюсь. Вот со знаковыми гарантий нет.

да, все работает и пререполнении.

алгоритмы для того чтобы поменять два числа в памяти машины

Алгоритм:

1. перегнать два слова по шине данных из памяти в регистры процессора
2. перегнать обратно в другом порядке

Всё остальное — абстракции. В сях ты можешь писать как угодно: специального оператора обмена в этом языке нет, но если у тебя нормальный промышленный компилятор, он твою временную переменную соптимизирует наиболее адекватным для конкретного набора команд способом.

Потому что у тебя архитектура такая, а вообще это ub (или impl-def, не помню лень искать).

Ой, кажись имена попутал, отмена.

Через XOR будет самый медленный способ, лучше всего через временную переменную.

Вот здесь все наглядно продемонстрировано:http://know-all.net/articles/view/60

Кстати, можете привести пример (с результатом), где это работать не будет?

Нет. Мне там инты померещились от другого регистранта, а на беззнаковых все ок.

Я скомпилировал и запустил Этот код. XOR и «разностный» подход по времени выполнения дают соизмеримые результаты. Конечно не понятно в каких случая и почему какой быстрее(это вообще уже погрешность на микропроцессорном уровне).

И ксор и разница генерят false dependency, а по времени могут отличаться только если интерферируют с флагами от окружающих команд. Со временной переменной должно быть быстрее, как уже заметили.

Шо, опять?

TL;DR: xor — метод Ъ-какеров, но медленный. Временная переменная — not so cool, но быстро.

наиболее интересно, на мой взгляд, — и узнать практические примеры того — для чего именно требуется менять местами два числа :)

[[ведь не для бесполезной пузырьковой сортировки?]]

Там у mdd анонимусов ломают, а он в ксор-свап тредах прохлаждается. Модератор блин.

Предлагаю запилить тест пузырек против схк-сорта и других убер-сортов для массива флотов размером например 23. Непосредственно итт.

да везде практически )

Соглашусь с джентльменом. Годная тема.

ОП, коли гонишься за быстротой, доверься оптимизации компилятора и втупую сделай всё с временной переменной. Компиляторы нынче часто умнее программистов и вовсе не грех этим пользоваться.

XOR swap - это клёво и ловко, но зависимо от архитектуры. И, надо заметить, это почти всегда медленнее и не всегда применимо. Так что, не нужно.

Ура! Очередное обсуждение xor vs. temp var на 35 страниц. Давненько не было. Царя внести не забудьте.

Царя внести не забудьте.

Что-то давненько его не было видно

Через XOR будет самый медленный способ

ксором в данном случае можно пользоваться только на МК, где нет памяти на доп. переменную

Царя внести не забудьте.

Что-то давненько его не было видно

мамка в лагерь отправила

Вот результат сравнения:

----------------------------
	Before Swap	
----------------------------
a=5
b=4
----------------------------
		After Swap:		
----------------------------
	Buffer variable:	
Elapsed time t=1.726060e-04 s
a=5, b=4
----------------------------
	Math Difference:	
Elapsed time t=1.485590e-04 s
a=5, b=4
----------------------------
	Bitwise XOR:	
Elapsed time t=1.542320e-04 s
a=5, b=4
----------------------------

теперь собери с -march=native -O2 / -O3

и объяви a и b как volataile, иначе компилятор всё свернёт в константу

1.Докажите теорему: пусть O-симметричная бинарная операция, а o ей обратная(и есть «нейтральный элемент»,т.е o можно как унарную для получения обратного, чтобы aoa=нейтральный) тогда обмен значений двух переменных:

        x=o(xOy)
        y=o(xOy)
        x=o(xOy)

2. покажите как обобщить на n-переменных n+1 присвоение(с некоторой n местной функцией) для получения любой перестоновки значений (rot, -rot и т.п)

_asm{ push a push b pop a pop b }

На сосфорже писали, что это медленней, чем через промежуточную переменную.

Надо законом запретить задавать этот вопрос на собеседованиях. А то достали. «Ой, а как переставить две переменные, не используя доп памяти?». Никак. Что-то я не уверен, что сложение или xor не используют какой-нибудь буфер.

Что-то я не уверен, что сложение или xor не используют какой-нибудь буфер.

Этот буфер называется регистры.

тупо через временную переменную причем одиночно используемую.

олени, пишущие на жаве и советующие докинуть матопераций - если вы не знаете как работает проц и что делает компилятор, пишите на жабе и врите людям

это не через промежуточную переменную, а через стек, который 99% времени в кеше L1

Всё остальное — абстракции.

И это тоже.

Не-а. RAM, шина данных центрального процессора и регистры — физически существующие объекты. Могу ткнуть пальцем, где конкретно (последнее — если электронный микроскоп дашь).

Да похоже с буферной переменной быстрее.

naman@smart:~/science/study$ gcc -o swap.o swap.c -march=native
naman@smart:~/science/study$ ./swap.o 
----------------------------
	Before Swap	
----------------------------
a=5
b=4
----------------------------
		After Swap:		
----------------------------
	Buffer variable:	
Elapsed time t=3.642000e-05 s
a=5, b=4
----------------------------
	Math Difference:	
Elapsed time t=6.479800e-05 s
a=5, b=4
----------------------------
	Bitwise XOR:	
Elapsed time t=6.521200e-05 s
a=5, b=4
----------------------------
As you can see XOR and Math Diff approach are commensurate!

«Native» means that the code produced will run only on that type of CPU. The applications built with -march=native on an AMD Athlon 64 CPU will not be able to run on an old VIA C3 CPU. Но мне кажется, что это уводит в сторону от того какой подход быстрее именно алгоритмически.

можно ещё через DMA сделать

но наверное для двух слов это будет оверхедом )

на последнем макбук про за 100000000 меняний одних и тех же волатильных переменных:

Tmp var time: 0.296741
xor time: 0.791380
math time: 0.791701

считал clock()'ом

Ну, поскльку нам всем опять делать нечего. ;)

package swap

func SwapXOR(a, b *int) {  
        *a ^= *b
        *b ^= *a
        *a ^= *b
}

func SwapTmp(a, b *int) {
        t := *a
        *a = *b
        *b = t
}

func SwapNative(a, b *int) {
        *a, *b = *b, *a
}

package swap

import "testing"

var (
        m = 10
        n = 20
)

func BenchmarkXOR(b *testing.B) {
        for i := 0; i < b.N; i++ {
                SwapXOR(&m, &n)
        }
}

func BenchmarkTmp(b *testing.B) {
        for i := 0; i < b.N; i++ {
                SwapTmp(&m, &n)
        }
}

func BenchmarkNative(b *testing.B) {
        for i := 0; i < b.N; i++ {
                SwapNative(&m, &n)
        }
}

$ go test -bench=.
testing: warning: no tests to run
PASS
BenchmarkXOR-4          200000000                6.10 ns/op
BenchmarkTmp-4          2000000000               1.60 ns/op
BenchmarkNative-4       2000000000               1.55 ns/op
ok      mystuff/swap    8.468s
$ go version
go version go1.5beta1 linux/amd64

опаньки. а как тогда устроена переменных местами в SwapNative? я думал, это разворачивается в то же, что и в SwapTmp.

Так оно как раз во что-то вроде *Tmp и разворачивается, но уже за кулисами.

что самое удивительное, это «вроде» работает быстрее, если я правильно понял.