رایانه‌ی باستانی

باستان‌شناسان در زمان حفاری شهر باستانی آتلانتیس به یک رایانه‌ی باستانی برخوردند که در عین سادگی دارای توانایی‌های بسیاری بود. بعد از انجام بررسی‌های اولیه مشخص شد که این رایانه برای انجام محاسبات، اعداد را به صورت نمایش در مبنای ۲ و در رشته‌های به طول ۳۲ از ارقام ۰ و ۱ نگهداری می‌کند. به هر یک از ارقام ۰ و ۱ در نمایش دودویی، یک ‎بیت گفته می‌شود و بیت‌ها را از سمت راست به چپ با اعداد ۰ تا ۳۱ شماره‌گذاری می‌کنیم. به عنوان مثال این رایانه برای ذخیره عدد ۲۷ رشته زیر را نگهداری می‌کند:

‎0000 0000 0000 0000 0000 0000 0001 1011

برای نگهداری اعداد، این رایانه یک حافظه‌‌ی ۲۶ خانه‌ای دارد که در هر خانه می‌تواند یک عدد ۳۲ بیتی را ذخیره کند. این خانه‌ها با حروف $‎$a‎ تا $‎z‎$ نام‌گذاری می‌شوند.

همچنین مشخص شده‌است این رایانه توانایی انجام عملیات‌های «و بیتی»، «یا بیتی»، «نقیض بیتی»، «شیفت بیتی به سمت راست»، جمع و ضرب را دارد.

‎‎برای نمایش راحت‌تر اعداد، هر عدد را به صورت یک عدد ۸ رقمی در مبنای ۱۶ نشان می‌دهیم. به عنوان مثال عدد ۲۷ را به صورت زیر نمایش می‌دهیم: (دقت کنید ارقام ‎۱۰‎,۱۱,‎⋯‎,۱۵ در مبنای ۱۶ با $A$, $B$ ,… ,$F$ نمایش داده می‌شوند)

‎0000001B‎

هر دستور در این رایانه، یکی از عملیات‌های بالا را روی اعداد ثابت یا اعداد درون حافظه‌ها اجرا کرده و نتیجه را در یکی از خانه‌های حافظه ذخیره می‌کند. دستورهای این رایانه به شکل زیر استفاده می‌شوند:

دستور عملکرد توضیح
ADD a,b,c مقدار حافظه ‎a‎ را برابر حاصل جمع ‎b‎ و ‎c‎ قرار می‌دهد
MLT a,b,c مقدار حافظه ‎a‎ را برابر حاصل ضرب ‎b‎ و ‎c‎ قرار می‌دهد
AND a,b,c مقدار حافظه ‎a‎ را برابر حاصل «و منطقی» ‎b‎ و ‎c‎ قرار می‌دهد بیت ‎$i$‎ام در حافظه ‎a‎ در صورتی برابر ‎۱‎ می‌شود که بیت ‎$i$ ‎ام هم در ‎b‎ و هم در ‎c‎ برابر ‎۱‎ باشد
OR a,b,c مقدار حافظه ‎a‎ را برابر حاصل «یا منطقی» ‎b‎ و ‎c‎ قرار می‌دهد
SHR a,b,c b‎ را ‎c‎ واحد به سمت راست شیفت داده و در ‎a‎ ذخیره می کند. مقدار ‎a‎ را برابر ‎$000...b_{31}b_{30}...b_c$ قرار می دهد(مقدار ‎b‎ تغییر نمی‌کند)
NOT a,b «نقیض منطقی» ‎b‎ را در ‎a‎ ذخیره می کند. بیت $‎i$ ‎ام در حافظه ‎a‎ در صورتی برابر ‎۱‎ می‌شود که بیت $‎i$‎ام در‎b‎ برابر ‎۰‎ باشد

هر برنامه در این کامپیوتر دنباله‌ای از دستورها است که به ترتیب اجرا می‌شوند. به عنوان مثال فرض کنید دو عدد در حافظه‌های ‎$a$‎ و ‎$b$‎ ذخیره شده‌اند. برنامه زیر مشخص می‌کند که حاصل جمع آن‌ها به ۲ بخش‌پذیر است یا نه (اگر بخش‌پذیر باشد عدد ۱ را در حافظه $‎$z‎ ذخیره می‌کند و در غیر این صورت عدد ۰ را در حافظه $‎z‎$ ذخیره می‌کند)

‎ADD c‎,‎a‎,‎b‎

‎AND d‎,‎c‎,‎00000001‎

‎NOT e‎,‎d‎

‎AND z‎,‎e‎,‎00000001‎

‎ بعد از انجام تحقیقات مرحله دوم مشخص شد که این رایانه دارای یک دستور عجیب نیز هست که تعداد بیت‌های در اندیس‌های زوج یک عدد که دارای مقدار ۱ هستند را در یک خانه حافظه ذخیره می‌کند. برای استفاده از این دستور باید به شکل زیر عمل کرد: CNT a‎,‎b‎ ‎ بعد از اجرای این دستور، تعداد بیت های ۱ در اندیس‌های زوج عدد در حافظه $b$ (یا عدد ثابت $b$)‎ در خانه‌ی حافظه $‎$a‎ ذخیره می‌شود. به عنوان مثال بعد از اجرای برنامه زیر، عدد ۲ در متغیر ‎$z$‎ ذخیره می‌شود، زیرا بیت‌های ‎$a_0$‎ و ‎a_2$‎$ دارای مقدار ۱ خواهند بود :

‎ADD a‎,‎00000002‎,‎00000005‎

‎CNT z‎,‎a‎

توجه: در هر قسمت‌ ابتدا برنامه‌ی خود را نوشته و سپس آن را در چند سطر توضیح دهید.

الف) برنامه‌ای بنویسید که با استفاده از ۴ دستور، تعداد بیت‌های با مقدار ۱ عددی را که در حافظه $‎$a‎ ذخیره شده است را در حافظه $‎$z‎ ذخیره کند.

ب) اولین برنامه‌ای که برای این کامپیوتر کشف شد، برنامه‌ای بود که تعداد تکرارهای رشته ۰۱ را در نمایش دودویی عددی که در حافظه ‎a$‎$ ذخیره شده است، به شرطی که ۰ در یک اندیس فرد و ‎۱‎ در یک اندیس زوج آمده باشد را محاسبه و در حافظه ‎z$‎$ ذخیره می‌کرد. به عنوان مثال اگر عدد درون حافظه $‎$a‎ برابر ‎DDABCDEF‎ باشد، این مقدار برابر ۳ است.

‎a = 1101 1101101010111100110111101111‎

برنامه‌ای با حداکثر ۴ دستور بنویسید تا این کار را انجام دهد. برای برنامه خود شیوه‌ی کارکرد آن را در چند سطر توضیح دهید.

پ) بعد از کشف برنامه‌ی قسمت قبل، محققان برنامه‌ای را پیدا کردند که عملکرد دستور ‎CNT‎ را شبیه‌سازی می‌کرد. اما متاسفانه یک عدد در دستور آخر برنامه قابل خواندن نبود. این برنامه به شکل زیر است:(می‌توانید فرض کنید عدد درون حافظه ‎a$‎$ برابر ‎۵۵۵۵۵۵۵۵‎ نیست)

‎AND b‎,‎a‎,‎55555555‎

‎SHR c‎,‎b‎,‎00000002‎

‎ADD d‎,‎b‎,‎c‎

‎AND e‎,‎d‎,‎33333333‎

‎MLT f‎,‎e‎,‎11111111‎

‎SHR z‎,‎f, ‎(…)

عدد مربوط به مکان خالی را کامل کنید و راه حل خود را توضیح دهید.