====== سوال ۲۴ ======



پس از اجرای الگوریتم زیر، مقدار $S$ چه خواهد بود؟

۱. $S$ را برابر ۰ قرار بده.

۲. به ازای $i$ از ۰ تا ۳۱ انجام بده:

۱-۲. به ازای $j$ از ۰ تا ۳۱ انجام بده:

۱-۱-۲. اگر $(i\ XOR\ j)$ از $i$ بزرگ‌تر شد، $S$ را یک واحد زیاد کن.
  - ۳۴۱
  - ۹۹۲
  - ۸۳
  - ۴۹۶
  - ۴۵۱

<راهنمایی>
به جایگاه بزرگ‌ترین بیت عدد 
$j$
زمانی که 
$i \, XOR \, j > j$
دقت کنید.
</راهنمایی>

<راهنمایی>
بزرگ‌ترین بیت عدد 
$j$
می‌بایست در جایگاهی قرار گیرد که در عدد 
$i$
در آن جایگاه عدد صفر واقع شده باشد.
</راهنمایی>

<راهنمایی>
چیستی باقی بیت‌های عدد 
$i$
و بیت‌های با ارزش کمتر 
$j$
اهمیتی ندارد.
</راهنمایی>
<راهنمایی>
بر روی جایگاه پر ارزش ترین بیت ۱ عدد 
$j$
حالت بندی کنید.
</راهنمایی>
<پاسخ>
 گزینه‌ی ۴ درست است.


تمام اعداد را به صورت اعداد پنج رقمی در نمایش مبنای ۲ می‌بینیم. فرض کنید
$a = (i\ XOR\ j)$
و
بیت $k$ ام (از سمت چپ) نخستین بیتی باشد که در عدد $i$ برابر ۰ و در $j$ برابر ۱ است (باید چنین بیتی موجود باشد، در غیر این صورت $a>i$ نمی‌شود).
برای آن که $a>i$ باشد، باید 
تا قبل از بیت $k$ ام، این حالت رخ ندهد که بیت متناظر در هر دو عدد $i$ و $j$ برابر ۱ باشد.
 پس 
$2^{k-1} \times 4^{5-k}=2^{9-k}$
حالت داریم. با در نظر گرفتن $k$ های مختلف،‌ پاسخ برابر
$$2^8+2^7+2^6+2^5+2^4 = 496$$
است.

</پاسخ>

  * [[سوال ۲۳|سوال قبل]]
  * [[سوال ۲۵|سوال بعد]]