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

الگوریتم جابه‌جایی یای انحصاری، الگوریتمی است که با استفاده از عملگر بیتی یای انحصاری مقدار دو متغیر را بدون استفاده از متغیر دیگری یا تغییر نوع متغیرها با یکدیگر جابه‌جا می‌کند.

الگوریتم

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

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. خاصیت جابه‌جایی: به ازای هر $A$ و $B$، $A\oplus B=B\oplus A$.
2. خاصیت شرکت‌پذیری: به ازای هر $A$ و $B$ و $C$ ، $A\oplus (B\oplus C)=(A\oplus B)\oplus C$.
3. وجود عضو خنثی: ۰ عضو خنثی است زیرا به ازای هر $A$، $A\oplus 0=0\oplus A=A$
4. وجود عضو وارون: هر عضو وارون خودش است زیرا به ازای هر $A$، $A\oplus A=0$.

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

مرحله	عملیات	ثبات R۱	ثبات R۲	ویژگی‌های استفاده شده
۰	تخصیص مقادیر	A	B	_
۱	R1 := R1 XOR R2	$A\oplus B$	B	_
۲	R2 := R2 XOR R1	$A\oplus B$	$(A\oplus B)\oplus B=A\oplus (B\oplus B)=A\oplus 0=A$	۲ و ۳ و ۴
۳	R1 := R1 XOR R2	$(A\oplus B)\oplus A=A\oplus (A\oplus B)=(A\oplus A)\oplus B=0\oplus B=B$	A	۱ و ۲ و ۳ و ۴

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

یای انحصاری را می‌توان به عنوان جمع دودویی و ۲ بیت را به عنوان یک بردار در میدان ۲ در نظر گرفت. در این‌صورت الگوریتم را می‌توان با ضرب یک ماتریس ۲ $\times$۲ در میدان ۲ معادل کرد. برای سادگی فرض می‌کنیم X و Y یک بیت باشند. در این‌صورت مرحله اول الگوریتم معادل خواهدبود با:

X := X XOR Y
Y := Y

که معادل ماتریسی آن ${\bigl (}{\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}{\bigr )}$است. داریم:

${\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\binom {X}{Y}}={\binom {X+Y}{Y}}$

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

${\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}$

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

برای تعمیم به وقتی که X و Y برادارهای بیتی به طول n اند، یای انحصاری معادل ماتریس ۲n $\times$۲n ${\bigl (}{\begin{smallmatrix}I_{n}&I_{n}\\0_{n}&I_{n}\end{smallmatrix}}{\bigr )}$است. باید توجه کرد که این ماتریس بر روی متغیرها (که در حافظه آدرس دارند) اعمال نمی‌شوند بلکه بر روی مقادیر اعمال می‌شوند.

نمونه کد

کد زیر، کد الگوریتم به زبان 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;
     }
 }

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

جستارهای وابسته

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