الگوریتم جابه‌جایی یای انحصاری کیست؟ توضیح بده.
الگوریتم جابه‌جایی یای انحصاری، الگوریتمی است که با استفاده از عملگر بیتی یای انحصاری مقدار دو متغیر را بدون استفاده از متغیر دیگری یا تغییر نوع متغیرها با یکدیگر جابه‌جا می‌کند.الگوریتم.الگوریتم به شرح زیر است:X := X XOR YY := Y XOR XX := X XOR Yاین الگوریتم معادل ۳ دستور در زبان ماشین است. همچنین چون یای انحصاری خاصیت جابه‌جایی دارد، دو عبارت X XOR Y و Y XOR X برابرند.این الگوریتم در حالتی که دو متغیر X و Y برابر باشند (منظور از برابری دو متغیر، یکی بودن آدرس آن‌هاست نه یکی بودن مقادیر آن‌ها)، به درستی کار نمی‌کند زیرا پس از خط اول مقدار X برابر 0 شده و چون آدرس X و Y یکی است، مقدار Y هم برابر 0 می‌شود و دو متغیر مقادیر واقعی خود را از دست می‌دهند.اثبات درستی الگوریتم.با استفاده از ویژگی‌های یای انحصاری.ویژگی‌های یای انحصاری عبارتند از:فرض کنید ثباتهای R۱ و R۲ به ترتیب دارای مقادیر A و B باشند، الگوریتم را برای R۱ و R۲ مرحله به مرحله اجرا می‌کنیم:با استفاده از جبر خطی.یای انحصاری را می‌توان به عنوان جمع دودویی و ۲ بیت را به عنوان یک بردار در میدان ۲ در نظر گرفت. در این‌صورت الگوریتم را می‌توان با ضرب یک ماتریس ۲ formula_12۲ در میدان ۲ معادل کرد. برای سادگی فرض می‌کنیم X و Y یک بیت باشند. در این‌صورت مرحله اول الگوریتم معادل خواهدبود با:X := X XOR YY := Yکه معادل ماتریسی آن formula_13است. داریم:formula_14دنباله دستورات الگوریتم را می‌توان به صورت ضرب ماتریس‌های ۲ formula_12۲ نشان داد:formula_16برای تعمیم به وقتی که X و Y برادارهای بیتی به طول n اند، یای انحصاری معادل ماتریس ۲n formula_12۲n formula_18است. باید توجه کرد که این ماتریس بر روی متغیرها (که در حافظه آدرس دارند) اعمال نمی‌شوند بلکه بر روی مقادیر اعمال می‌شوند.نمونه کد.کد زیر، کد الگوریتم به زبان C است: void xorSwap (int *x, int *y) if (x != y) *x ^= *y; *y ^= *x; *x ^= *y;باید توجه‌کرد که کد ابتدا بررسی می‌کند که آیا آدرس دو متغیر یکی است یا خیر زیرا اگر یکی باشد، همان‌گونه که پیش از این گفته‌شد مقدار متغیر ۰ خواهدشد. همچنین می‌توان الگوریتم را به صورت یک ماکرو تعریف کرد:/* درصورتی که دو متغیر برابر باشند، به درستی کار نمی‌کند. *//* ابتدا یکی نبودن آدرس‌ها را بررسی می‌کند، سپس دو متغیر را جابه‌جا می‌کند. */دلایل استفاده از الگوریتم.در بیشتر موارد در عمل استفاده از یک ثبات دیگر برای جابه‌جایی بهینه‌تر است و در موارد محدودی جابه‌جایی با یای نحصاری ممکن است در عمل به کار بیاید مانند:دلایل عدم استفاده از الگوریتم.بیشتر کامپایلرهای جدید متغیرهای موقت را پس از استفاده، آزاد می‌کنند لذا از نظر حافظه و زمان الگوریتم جابه‌جایی سه طرفه با این الگوریتم تفاوتی ندارد. ضمن آنکه این الگوریتم برای کسی که با روش آن آشنا نباشد نامفهوم است.در کامپوترهای جدید، الگوریتم جابه‌جایی یای انحصاری از الگوریتم جابه‌جایی سه طرفه کنتر است. از پردازنده‌های x۸۶ اینتل و ای‌ام‌دی به بعد، جابه‌جایی بین ثبات‌ها بدون تأخیر انجام می‌شود. حتی اگر ثباتی برای استفاده نباشد، دستور XCHG حداقل به اندازه سه عملیات یای انحصاری سریع خواهدبود. دلیل دیگر آن است که پردازنده‌ها حتی‌الامکان دستورات را موازی اجرا می‌کنند. در الگوریتم یای انحصاری، ورودی‌های هر عملگر به خروجی مرحله قبل بستگی دارد لذا نمی‌توان مراحل آن را موازی اجرا کرد.تعمیم به دیگر عملگرها.در این الگوریتم، یای انحصاری می‌تواند با هر عملگری که ۴ خاصیت گفته‌شده را داشته‌باشد، جایگزین شود. با جایگزین کردن یای انحصاری با جمع و تفریق خواهیم‌داشت:void addSwap (unsigned int *x, unsigned int *y) if (x != y) *x = *x + *y; *y = *x - *y; *x = *x - *y;برخلاف یای انحصاری، در این نوع پردازنده یا زبان برنامه‌نویسی استفاده‌شده باید از هم‌نهشتی یا اعداد بزرگ استفاده کنند تا بتوان مطمئن شد که عملگرها سرریز ندارند؛ لذا کاربرد این از کاربرد یای انحصاری کمتر خواهدبود.