Препълване на стека по време на SWAP

Как можем да се погрижим за препълването, което се случва по време на размяната на две променливи, без да използваме трета променлива. Вярвам, че решението XOR може да се използва само за цели числа. какво ще кажете за другите типове променливи?


person Community    schedule 04.04.2009    source източник
comment
други видове като ..? на какъв език, между другото?   -  person Aziz    schedule 05.04.2009
comment
Само предчувствие... това няма да е C++ със суап, който се случва в копиращ конструктор, нали?   -  person Vilx-    schedule 05.04.2009


Отговори (6)


Това не е отговор, но не се вписва в коментар.

При какви обстоятелства бихте работили толкова близо до ръба на наличното ви хранилище на стека, че допълнителното използване на временна променлива за суап ще ви създаде затруднения?

Мога да видя някои вградени сценарии, но ми е трудно да си представя сценарий, при който сте толкова ограничени в стековото пространство, че това би имало значение (където не пишете код на асемблер).

person ReinstateMonica Larry Osterman    schedule 04.04.2009

XOR ще работи за всичко, което можете да накарате вашия XOR оператор да обработи; това е свойство на двоични данни, а не на двоични данни, използвани за представяне на цели числа.

person chaos    schedule 04.04.2009
comment
Само ако операторът XOR действително изпълнява операция XOR, а не ако е бил претоварен, за да направи нещо странно (на език, който позволява претоварване на оператор, т.е.). - person David Z; 05.04.2009
comment
Уф; да, това е вярно и си струва да се спомене. Благодаря. - person chaos; 05.04.2009
comment
Така че прехвърлете данните обратно към целочислен или char масив и направете xor върху елементите от това. - person paxdiablo; 05.04.2009

Като не го правя изобщо. Алгоритъмът за размяна на XOR е страхотен хак. Той не трябва да се използва в производствения код.

person sigjuice    schedule 04.04.2009

Решението XOR работи с всеки тип, който може да бъде побитово копиран, не само с цели числа. Въпреки това, не XOR променлива със себе си: т.е.

int x = 10;
int *p1 = &x;
int *p2 = p1;

*p1 = *p1 ^ *p2;
*p2 = *p1 ^ *p2;
*p1 = *p1 ^ *p2;

/* now x == 0 :( */
person rlbond    schedule 04.04.2009

Какво не е наред с XCHG? Не е необходим стек, няма препълване (флаг за пренасяне)? задайте или :).

person RandomNickName42    schedule 02.07.2009
comment
Прочетете връзката в този отговор и след това следвайте бележка под линия 2 и я прочетете. Накратко - обърква кеша на процесора, като по този начин забавя нещата. stackoverflow.com/questions/717935/stack-overflow- по време на размяна/ - person Vilx-; 02.07.2009
comment
Опа, трябва да бъда по-внимателен с щракването си, всъщност не исках да гласувам за този коментар, но се наслаждавайте на идеята;) Прочетох отново ръководството с инструкции на Intel за XCHG и забелязах наказание за кеша само при неестествено подравняване достъп до дадените операнди. Може би пропускам нещо, но можете да вградите XCHG в C/C++ в по-голямата си част, освен 64-битов MSVC и мисля, че удовлетворява въпроса за неизползване на стека при размяна на 2 променливи, включително използването на нецелочислени типове . Освен това, както бяха попитали други, този въпрос всъщност дори не изглежда да е специфичен за езика, така че Ассамблеята е A-OK IMHO :) - person RandomNickName42; 02.07.2009

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

Това ще работи за цели числа и float.

person tefozi    schedule 02.07.2009
comment
Прочетете връзката в този отговор и след това следвайте бележка под линия 2 и я прочетете. Накратко - отнема повече памет и цикли на процесора, отколкото простата размяна. stackoverflow.com/questions/717935/stack-overflow- по време на размяна/ - person Vilx-; 02.07.2009