Поменять местами две переменные с помощью XOR

С помощью следующего метода мы можем поменять местами две переменные A и B

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

Я хочу реализовать такой метод на С++, который работает со всеми типами (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 МБ ресурсов, но делится ими с другими своими экземплярами. Если вы проигнорируете логику класса и выполните операцию XOR, у вас будет 3x10 МБ операции XOR. Конструктор перемещения, в свою очередь, скопирует только несколько указателей. Это, конечно, теоретическая ситуация, но суть вы поняли.   -  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 Мб. Другие экземпляры хранят указатели на данные в этом классе (по дизайну). Помимо долгой работы, это также может повредить классы. ИМО, опускание операторов перемещения/копирования или операторов присваивания во время такого обмена также является плохой идеей.   -  person Spook    schedule 13.06.2014
comment
@Spook Если sizeof(class) == 10 МБ, правильный конструктор перемещения должен, тем не менее, касаться всех 10 МБ. Перемещение может быть быстрее копирования, только если есть что-то, что не включено в сам объект, т.е. е. размещены в куче. Но мы уходим далеко от темы.   -  person cmaster - reinstate monica    schedule 13.06.2014
comment
@cmaster Что может привести к совершенно бессмысленным результатам. Например, если структура содержит указатель на часть самой себя, такой обмен приведет к тому, что каждая структура будет содержать указатель на часть другой!   -  person David Schwartz    schedule 10.05.2016
comment
@DavidSchwartz Теперь я понимаю, к чему клонил Призрак. Мне просто никогда не приходило в голову, что кто-то может объявить такой огромный класс и использовать только его небольшие части, оставив остальные неинициализированными. Для моего мозга объекты всегда малы (большие данные распределяются ими динамически) и полностью инициализированы (все это всегда находится в точно определенном состоянии)... Думаю, если у вас есть класс размером 10 МБ, который делает не использует большие части выделенного ему пространства, гораздо важнее реорганизовать его во что-то разумное, чем думать о производительности операции подкачки на нем.   -  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 (ситуация, которая возникает в большинстве случаев реального использования свопа). - 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