Разменете две променливи с XOR

Със следния метод можем да разменим две променливи A и B

A = A XOR B
B = A XOR B
A = A XOR B

Искам да внедря такъв метод в C++, който работи с всички типове (int, float, char, ...), както и структури. Както знаем, всички видове данни, включително структури, заемат определено място в паметта, например 4 байта, 8 байта

По мое мнение този метод за размяна трябва да работи с всички типове, с изключение на базирани на указател типове, той трябва да разменя съдържанието на паметта, тоест битове, на две променливи

Моят въпрос
Нямам идея как мога да внедря такъв метод в C++, който работи със структури (те не съдържат никакви указатели). Може ли някой да ми помогне?


c++ xor
person frogatto    schedule 13.06.2014    source източник
comment
@ThorstenDittmar прав сте, сър, но не искам да използвам допълнителна променлива   -  person frogatto    schedule 13.06.2014
comment
Просто използвайте std::swap.   -  person Luchian Grigore    schedule 13.06.2014
comment
@harold Не, за този въпрос искам да разменя две структури   -  person frogatto    schedule 13.06.2014
comment
Вече имате такава функция на ваше разположение. Казва се std::swap(...). cplusplus.com/reference/algorithm/swap   -  person clstrfsck    schedule 13.06.2014
comment
@LuchianGrigore Вие сте прав, сър, но искам да внедря своя собствена функция, която използва XOR   -  person frogatto    schedule 13.06.2014
comment
Ако искате да приложите своя собствена функция... направете го. Ако срещнете проблеми, задайте конкретен въпрос тук.   -  person nvoigt    schedule 13.06.2014
comment
@ABFORCE И защо не искате да използвате временна променлива?   -  person Spook    schedule 13.06.2014
comment
@cmaster Или move-ctors, което ще направи тази операция много по-бърза, използвайки временна променлива, отколкото XOR-то на тяхното съдържание.   -  person Spook    schedule 13.06.2014
comment
@Spook Трябва да не се съглася със скоростта тук, защото можете да направите трика XOR с възможно най-големия тип, което го прави по-бърз от движението. Преместването е само по-бързо от дълбокото копиране.   -  person cmaster - reinstate monica    schedule 13.06.2014
comment
можете да предположите, че това е училищна задача :) - тогава опитайте да си направите домашното, преди да помолите другите да го направят.   -  person Tony Delroy    schedule 13.06.2014
comment
Истинският проблем е, че това не работи във всички случаи. Всяка рутина за размяна трябва да обработва случаи, когато кодът извиква функцията с два аргумента, отнасящи се до една и съща променлива, по редовете на std::swap( a, a ). Алгоритъмът xor не работи в този случай и затова е безполезен като обща рутина за размяна.   -  person James Kanze    schedule 13.06.2014
comment
@cmaster Представете си клас, който държи 10 Mb ресурси, но ги споделя с другите си инстанции. Ако пренебрегнете логиката на класа и ги изведете чрез XOR, ще имате 3x10Mb XORing. Конструкторът за преместване от своя страна ще копира само няколко указателя. Това е теоретична ситуация, разбира се, но схващате смисъла.   -  person Spook    schedule 13.06.2014
comment
@Spook Не, ще имате много бързо XOR от sizeof(class), ако приложите XOR трика към класа. Тъй като игнорира логическото съдържание на класа, трикът XOR няма да преследва управляваната памет, а просто ще размени указателите.   -  person cmaster - reinstate monica    schedule 13.06.2014
comment
@cmaster sizeof(class) = 10 Mb. Други екземпляри поддържат указатели към данни в този клас (по дизайн). Освен дълга работа, това може да навреди и на класовете. IMO, пропускането на оператори за преместване/копиране или оператори за присвояване по време на такъв обмен също е лоша идея.   -  person Spook    schedule 13.06.2014
comment
@Spook Ако sizeof(class) == 10 MB, правилният конструктор на движение трябва въпреки това да докосне всичките 10 MB. Преместването може да бъде по-бързо от копирането само ако има нещо, което не е включено в самия обект, т.е. д. разпределени в купчината. Но тук много се отклоняваме от темата.   -  person cmaster - reinstate monica    schedule 13.06.2014
comment
@cmaster Което може да доведе до напълно безсмислени резултати. Например, ако структурата съдържа указател към част от себе си, размяната по този начин ще доведе до всяка структура, съдържаща указател към част от другата!   -  person David Schwartz    schedule 10.05.2016
comment
@DavidSchwartz Сега разбирам какво цели Spook. Просто никога не ми е хрумвало, че някой може да декларира такъв огромен клас и да използва само малки части от него, оставяйки останалите неинициализирани. За моя мозък обектите винаги са малки (големи данни се разпределят динамично от тях) и напълно инициализирани (цялото нещо е в перфектно дефинирано състояние през цялото време)... Предполагам, че ако имате 10 MB клас, който прави не използва големи части от разпределеното му пространство, много по-належащо е да го преработите в нещо разумно, отколкото да мислите за изпълнението на операция за размяна върху него.   -  person cmaster - reinstate monica    schedule 10.05.2016

Отговори (2)


arrow_upward
2
arrow_downward

Вашият проблем лесно се свежда до xor-swap буфери на сурова памет. Нещо такова.

void xorswap(void *a, void *b, size_t size);

Това може да се приложи по отношение на xorswaps примитивни типове. Например:

void xorswap(void *a, void *b, size_t size)
{
    if (a == b)
        return; //nothing to do

    size_t qwords = size / 8;
    size_t rest = size % 8;

    uint64_t *a64 = (uint64_t *)a;
    uint64_t *b64 = (uint64_t *)b;
    for (size_t i = 0; i < qwords; ++i)
        xorswap64(a64++, b64++);
    uint8_t *a8 = (uint8_t*)a64;
    uint8_t *b8 = (uint8_t*)b64;
    for (size_t i = 0; i < rest; ++i)
        xorswap8(a8++, b8++);
}

Оставям изпълнението на xorswap64() и xorswap8() като упражнение на читателя.

Също така имайте предвид, че за да бъдат ефективни, оригиналните буфери трябва да бъдат 8-байтови. Ако това не е така, в зависимост от архитектурата кодът може да работи неоптимално или изобщо да не работи (отново упражнение за читателя ;-).

Възможни са и други оптимизации. Можете дори да използвате устройството на Дъф, за да развиете последния цикъл, но не знам дали заслужава си. Ще трябва да го профилирате, за да знаете със сигурност.

person rodrigo    schedule 13.06.2014
comment
Както вече посочих в коментарите: Дори е опасно да се предоставя такава функция. Не е гарантирано, че ще направите нещо дистанционно правилно на всички структури. - person cmaster - reinstate monica; 13.06.2014
comment
За да направите това по-общо, може да искате да смесите CHAR_BIT или поне да използвате sizeof(uint64_t) вместо 8. - person Angew is no longer proud of SO; 13.06.2014
comment
@cmaster: Да, опасно е, но е така memcpy(). Никога не бих използвал този код в реална програма (съмнявам се, че ще даде някакво предимство пред временното), но е добър като упражнение по програмиране. - person rodrigo; 13.06.2014
comment
Истинският проблем е, че всъщност не работи. Опитайте, когато a == b (ситуация, която се среща при повечето реални употреби на swap). - person James Kanze; 13.06.2014
comment
@Angew: Е, на теория си прав, разбира се. Но на практика CHAR_BIT е 8 за повечето архитектури, които интересуват повечето хора. Ако CHAR_BIT беше, да речем, 7, тогава не знам как компилаторът би имплементирал uint8_t или дори uint64_t. - person rodrigo; 13.06.2014
comment
И разбира се, използването на unsigned long long вместо uint64_t ще доведе до по-добра преносимост. - person James Kanze; 13.06.2014
comment
@JamesKanze: О! имаш предвид, когато блоковете памет са еднакви. Лесна проверка, или ако предпочитате, можете да проверите за това в помощните функции xorswap64() и xorswap8(). - person rodrigo; 13.06.2014
comment
@cmaster: Този трик ще работи правилно върху тривиално копируеми структури. Стандартът C++ ви дава свободата да разчитате на това или да се простреляте в крака, ако не е така. - person david.pfx; 13.06.2014
comment
@JamesKanze: Работи добре при равни стойности, но не и при припокриваща се памет. Но това важи и за memcpy() и е известно, че разчитам на това. - person david.pfx; 13.06.2014
comment
@david.pfx: Моята функция не осъществява достъп до памет извън даденото size. Ако го наречете по този начин xorswap(&s1, &s2, sizeof(s1)), бидейки s1 и s2 от един и същи (тривиално копируем) тип, не виждам проблема. - person rodrigo; 13.06.2014

arrow_upward
0
arrow_downward

Можете да използвате Bitwise XOR "^" в C за XOR два бита. Вижте тук и тук. Сега за XOR 'a' и 'b' започнете XOR от източния значим бит към най-значимия бит.

person Parag Gangil    schedule 13.06.2014