پس از اجرای الگوریتم زیر، مقدار $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$$ است.