الگوریتم جابجایی مقادیر بدون متغیر موقتی

معمولا وقتی نیاز به جابجایی مقدار دو متغیر مانند x و y داریم متغیر سومی با نامی همچون temp ایجاد کرده و از آن استفاده می‌کنیم. آیا راه دیگری برای جابجایی مقادیر متغیرها بدون متغیر سومی وجود دارد؟!

26 آبان‌ماه 1395
محمد فرهمند

همواره موقعیت هایی پیش می‌آید که نیاز به جابجایی مقدار دو متغیر داریم و این کار عموما با ایجاد متغیر سومی انجام می‌شود. اما راه دیگری نیز برای جابه‌جایی مقادیر دو متغیر وجود دارد که به الگورتیم XOR Swap شهرت دارد و نیازی به متغیر سوم ندارد. همانطور که از نام این متغیر پیداست قصد داریم از عملگر XOR برای این کار استفاده کنیم.

فرض کنید می‌خواهیم مقدار دو متغیر x = 10 و y = 3 را جابه‌جا کنیم. معمولا بدین منظور از دستورات زیر استفاده می‌شود:

کد زیر نیز دقیقا کار دستورات بالا را انجام می‌دهد با این تفاوت که نیازی به متغیر temp ندارد:

عملگر xor در زبان C با نماد ^ نمایش داده می‌شود.

همانطور که در تصویر فوق می‌بینید در خط نخست مقدار x xor y را درون x ذخیره کرده‌ایم که برابر 9 شده است. سپس مقدار تازه x را با مقدار y xor می کنیم که حاصل آن برابر ده است (مقدار اولیه x هم اکنون در y ذخیره شده) در خط سوم نیز xor مقدار تازه x با مقدار نسختینش مقدار y را به ما می‌دهد! در واقع xor یک ابزار عالی برای ذخیره اطلاعات به صورت رمزنگاری شده است. زیرا با تکرار عمل xor می‌توان به سادگی به مقدار پیشین رسید. بیایید نگاهی عمیق‌تر به دستورات فوق بیندازیم:

  • در نخستین مرحله مقدار x را با انجام عمل xor با y به مقدار ترکیبی آن تبدیل می‌کنیم.
  • در مرحله دوم عمل xor را با مقدار تازه x و مقدار اصلی y انجام می‌دهیم. تکرار عمل xor تمام اطلاعات y را حذف کرده و تنها مقدار x را به جا می‌گذارد که قبل‌تر با y ترکیب شده بود. در واقع با تکرار عمل xor مقدار y از ترکیب با x خارج شد و تنها x باقی ماند.
  • در مرحله آخر متغیر x هنوز مقداری ترکیبی دارد. بنابرین با تکرار عمل xor اطلاعات x را از آن خارج می‌کنیم تا تنها مقدار y بر جا بماند و آن را در y ذخیره می‌کنیم.

اما آیا استفاده از این الگوریتم واقعا ما را از ایجاد یک متغیر سوم بی‌نیاز می‌کند؟ هنگامی که زبان برنامه‌نویسی به عملگر xor (یا به طور کلی هر عملگری) برسد، ALU حاصل عملیات را محاسبه کرده و در Register اصلی ذخیره می‌کند. پس همچنان برای انجام عملیات به متغیر سومی نیاز است اما این بار متغیر در CPU و نه در RAM ذخیره می‌شود. چون معمولا کسی به فکر CPU بیچاره نیست و تنها مقدار حافظه‌ای که برنامه اشغال می‌کند مد نظر است این الگوریتم جادویی به نظر می‌رسد!

2 پاسخ به “الگوریتم جابجایی مقادیر بدون متغیر موقتی”

  1. Arash گفت:

    واقعا جالب بود.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *