Я слышал от моего друга, что лучшим алгоритмом для обмена является "(a^= b^= a^= b)" где a и b - два целых числа, подлежащих обмену. , но когда я применил это с использованием языка c, это привело к сбою. Может ли кто-нибудь из вас прекрасных людей объяснить возможную причину этого? , пожалуйста, предложите лучший алгоритм для обмена. спасибо !!!! ребята, я хотел бы знать причину сбоя.лучший алгоритм для обмена?
этот обменный трюк иногда опасен, я видел неправильную программу быстрой сортировки с использованием этой подкачки, которая порождает неверные результаты. Но обычная свопа генерирует правильную программу.
С уважением к скорости компилятор иногда генерирует более быстрый код, если мы используем переменную tmp.
использование tmp = a; a = b; b = tmp;
спасибо @yin Мне хотелось бы знать, почему мой трюк очень опасен? –
XOR swap ('a^= b^= a^= b') будет работать только с целыми числами (и указателями). XOR swap изменит как 'a', так и' b' на 0, если они равны. – LiraNuna
Предположим, что 'a' и' b' - указатели, указывающие на одно и то же. Тогда '(* a)^= (* b)^= (* a)^= (* b)' будет обнулять значение. В C++, если это ссылки, вы можете сделать это без разыменования. Но настоящая причина использовать то, что @Yin Zhu предлагает, заключается в том, что ваш код должен быть четким, и вам не стоит беспокоиться о такой микро-оптимизации. – rlbond
Используйте эту логику для числовых значений:
int a = 10, b =5 ;
a = a-b;
b = b+a ; // b gets the original value of a
a = b - a; // a gets the original value of b
printf ("value : %d %d \n",a ,b) ;
Что происходит, когда 'a' является' INT_MAX', а 'b' является' INT_MIN'? Другими словами, 'a-b' может переполняться/переполняться. –
@Alok: Несмотря на переполнение, он все равно даст правильный ответ с арифметикой обволакивания. – dan04
@ dan04: wraparound не гарантируется - в C/C++ целочисленное переполнение UB. –
См http://en.wikipedia.org/wiki/Swap_(computer_science).
Использование временной переменной генерирует больше накладных расходов, но более стабильно, чем алгоритм обмена XOR, а параллельные вычисления делают его быстрее, чем замена XOR.
См. Пример первого кода http://www.ibm.com/developerworks/linux/library/l-metaprog1.html для надежной реализации использования временной переменной для свопинга.
Почему это создает дополнительные накладные расходы для решения временной переменной? Смена XOR также создает дополнительные вычислительные накладные расходы. – phoxis
a^=b^=a^=b;, возможно, сбой, потому что он вызывает страшное поведение . Правило, которое он ломает, состоит в том, что он дважды меняет a без промежуточной точки последовательности. Это может быть исправлено путем введения некоторых точек последовательности - например, с помощью оператора запятая:
a ^= (b ^= a ^= b, b);`
Или разбить его на несколько утверждений:
b ^= a ^= b; a ^= b;
Это по-прежнему, однако, как правило, плохо метод для замены переменных - некоторые из других ответов и комментариев достаточно объяснили, почему.
Напишите этот код, который быстрее читается человеком. И способность компиляторов доверия генерировать лучший код большую часть времени. Сделайте профилирование, чтобы убедиться, что это единственное место для улучшения скорости. Затем примените XOR-решения, перечисленные много раз выше, он может работать не везде.
Я не могу поверить, что это даже вопрос о SO. Что случилось с 'std :: swap'? –
@BillyIneal: поскольку std :: swap - это C++, и этот вопрос помечен C. – LiraNuna
OK - Извините. Позвольте мне изменить это на «Что не так с простой простой реализацией, типичной для' std :: swap'? 'T temp = one; one = two; two = temp; 'Seriously - если swap является ограничителем скорости вашей программы, тогда у вас есть проблема, я бы точно хотел. –