الگوریتم جابه‌جایی یای انحصاری

الگوریتم به شرح زیر است:

X := X XOR Y
Y := Y XOR X
X := X XOR Y

این الگوریتم معادل ۳ دستور در زبان ماشین است. همچنین چون یای انحصاری خاصیت جابه‌جایی دارد، دو عبارت X XOR Y و Y XOR X برابرند.

این الگوریتم در حالتی که دو متغیر X و Y برابر باشند (منظور از برابری دو متغیر، یکی بودن آدرس آن‌هاست نه یکی بودن مقادیر آن‌ها)، به درستی کار نمی‌کند زیرا پس از خط اول مقدار X برابر ۰ شده و چون آدرس X و Y یکی است، مقدار Y هم برابر ۰ می‌شود و دو متغیر مقادیر واقعی خود را از دست می‌دهند.

اثبات درستی الگوریتم

با استفاده از ویژگی‌های یای انحصاری

ویژگی‌های یای انحصاری عبارتند از:

1. خاصیت جابه‌جایی: به ازای هر ${\displaystyle A}$
   و ${\displaystyle B}$
   ، ${\displaystyle A\oplus B=B\oplus A}$
   .
2. خاصیت شرکت‌پذیری: به ازای هر ${\displaystyle A}$
   و ${\displaystyle B}$
   و ${\displaystyle C}$
   ، ${\displaystyle A\oplus (B\oplus C)=(A\oplus B)\oplus C}$
   .
3. وجود عضو خنثی: ۰ عضو خنثی است زیرا به ازای هر ${\displaystyle A}$
   ، ${\displaystyle A\oplus 0=0\oplus A=A}$
4. وجود عضو وارون: هر عضو وارون خودش است زیرا به ازای هر ${\displaystyle A}$
   ، ${\displaystyle A\oplus A=0}$
   .

فرض کنید ثباتهای R۱ و R۲ به ترتیب دارای مقادیر A و B باشند، الگوریتم را برای R۱ و R۲ مرحله به مرحله اجرا می‌کنیم:

R1 := R1 XOR R2

R2 := R2 XOR R1

R1 := R1 XOR R2

با استفاده از جبر خطی

یای انحصاری را می‌توان به عنوان جمع دودویی و ۲ بیت را به عنوان یک بردار در میدان ۲ در نظر گرفت. در این‌صورت الگوریتم را می‌توان با ضرب یک ماتریس ۲ ${\displaystyle \times }$

X := X XOR Y
Y := Y

که معادل ماتریسی آن

دنباله دستورات الگوریتم را می‌توان به صورت ضرب ماتریس‌های ۲ ${\displaystyle \times }$

(چون جمع در میدان ۲ است، ۰ = ۱ + ۱)

برای تعمیم به وقتی که X و Y برادارهای بیتی به طول n اند، یای انحصاری معادل ماتریس ۲n ${\displaystyle \times }$

کد زیر، کد الگوریتم به زبان C است:

 void xorSwap (int *x, int *y)
 {
     if (x != y)
     {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

باید توجه‌کرد که کد ابتدا بررسی می‌کند که آیا آدرس دو متغیر یکی است یا خیر زیرا اگر یکی باشد، همان‌گونه که پیش از این گفته‌شد مقدار متغیر ۰ خواهدشد. همچنین می‌توان الگوریتم را به صورت یک ماکرو تعریف کرد:

#define XORSWAP_UNSAFE(a, b) ((a)^=(b),(b)^=(a),(a)^=(b))
/* درصورتی که دو متغیر برابر باشند، به درستی کار نمی‌کند. */
#define XORSWAP(a, b)   ((&(a) == (b)) ? (a) : ((a)^=(b),(b)^=(a),(a)^=(b)))
/* ابتدا یکی نبودن آدرس‌ها را بررسی می‌کند، سپس دو متغیر را جابه‌جا می‌کند. */

در بیشتر موارد در عمل استفاده از یک ثبات دیگر برای جابه‌جایی بهینه‌تر است و در موارد محدودی جابه‌جایی با یای نحصاری ممکن است در عمل به کار بیاید مانند:

• در پردازنده که با توجه به مجموعه دستورالعمل، جابه‌جایی با یای انحصاری به تعداد کمتری بیت کد می‌شود.
• در ریزکنترل‌گرها که حافظه محدود است.
• در کاربردهای رمزنگاری که توابع باید دارای زمان ثابت باشند تا از حملات وابسته زمان جلوگیری شود.

بیشتر کامپایلرهای جدید متغیرهای موقت را پس از استفاده، آزاد می‌کنند لذا از نظر حافظه و زمان الگوریتم جابه‌جایی سه طرفه با این الگوریتم تفاوتی ندارد. ضمن آنکه این الگوریتم برای کسی که با روش آن آشنا نباشد نامفهوم است.

در کامپوترهای جدید، الگوریتم جابه‌جایی یای انحصاری از الگوریتم جابه‌جایی سه طرفه کنتر است. از پردازنده‌های x۸۶ اینتل و ای‌ام‌دی به بعد، جابه‌جایی بین ثبات‌ها بدون تأخیر انجام می‌شود. حتی اگر ثباتی برای استفاده نباشد، دستور XCHG حداقل به اندازه سه عملیات یای انحصاری سریع خواهدبود. دلیل دیگر آن است که پردازنده‌ها حتی‌الامکان دستورات را موازی اجرا می‌کنند. در الگوریتم یای انحصاری، ورودی‌های هر عملگر به خروجی مرحله قبل بستگی دارد لذا نمی‌توان مراحل آن را موازی اجرا کرد.

در این الگوریتم، یای انحصاری می‌تواند با هر عملگری که ۴ خاصیت گفته‌شده را داشته‌باشد، جایگزین شود. با جایگزین کردن یای انحصاری با جمع و تفریق خواهیم‌داشت:

void addSwap (unsigned int *x, unsigned int *y)
 {
     if (x != y)
     {
         *x = *x + *y;
         *y = *x - *y;
         *x = *x - *y;
     }
 }

برخلاف یای انحصاری، در این نوع پردازنده یا زبان برنامه‌نویسی استفاده‌شده باید از هم‌نهشتی یا اعداد بزرگ استفاده کنند تا بتوان مطمئن شد که عملگرها سرریز ندارند؛ لذا کاربرد این از کاربرد یای انحصاری کمتر خواهدبود.

• تفاضل متقارن
• شبکه فایستل