سوال ۱۹

گزینه‌ی «۲» درست است.

ابتدا باید توجه داشته باشیم که نمایش دودویی عدد$⌊\frac{x}{2}⌋$همانند عدد $x$ است با این تفاوت که راست ترین رقم آن حذف شده است . نمایش دودویی عدد$⌊\frac{x}{4}⌋$هم همانند $x$ است با این تفاوت که دو رقم سمت راست آن حذف شده است .

در مرحله ی اول بررسی الگوریتم ، می خواهیم ببینیم با رسیدن به خط 4 برنامه ، $y$ چه عددی را نشان می‌دهد . با توجه به توضیح بالا در هر بار اجرای خط 2 ، رقم سمت راست $x$ خذف شده و عدد جدید با $y$ ،$XOR$ می شود. به این ترتیب می‌توان گفت به ازای رقم $k$ ام نمایش دودویی $x$ ،$XOR$ آن رقم با رقم های سمت چپ آن در جای رقم $k$ام نمایش دودویی $y$ قرار داده می شود.

حال باید ببینیم $z$ در چه صورت صفر است. در طی اجرای الگوریتم ابتدا اولین رقم سمت راست نمایش دودویی $y$ را به $z$ اضافه کرده سپس دوبرابر می‌کنیم. پس از آن رقم سوم نمایش دودویی $y$ را به $z$ اضافه کرده و آن را دو برابر می‌کنیم و پس از آن رقم پنجم ، هفتم و … . در هیچ یک از این مراحل رقم اضافه شده به $z$ نباید صفر باشد. بنابراین $z$ در صورتی صفر است که از سمت راست نمایش دودویی $y$ رقم اول ، سوم ، پنجم ، هفتم و … صفر باشد .

اگر $y$ فردرقم داشته باشد در نمایش دودویی آخرین رقمی که به $z$ اضافه می‌شود سمت چپ ترین رقم $y$ در نمایش دودویی آن است . از آن‌جایی که این رقم 1 است پس $z$ دیگر صفر نخواهد بود.

اما اگر $y$ زوج رقم داشته باشد ، در نمایش دودویی سمت چپ ترین رقم 1 است. اما چون رقم بعدی آن (دومین رقم از سمت چپ) در جایگاه رقم فرد قرار دارد پس باید 0 باشد. بنابراین این رقم باید در $x$ یک باشد تا $XOR$ آن با آخرین رقم برابر صفر شود .(زیرا این رقم به $z$ اضافه می‌شود) . بعد این دو رقم باید $XOR$ رقم سوم و چهارم از سمت چپ نمایش دودویی $x$ ، 0 باشد.(چون $XOR$ چهار رقم اول از سمت چپ در جای چهارمین رقم از سمت چپ $y$ قرار می‌گیرد. به همین ترتیب $XOR$ رقم پنجم و ششم هم باید صفر باشد . و پس از آن هم به همین ترتیب. پس اگر این ارقام را دوتا دوتا دسته بندی کنیم همه‌ی دسته‌ها به جز چپ‌ترین دسته که یک حالت دارد ، دو حالت دارند (11 یا 00) .

حال با توجه به تعداد ارقام $x$ ، تعداد حالات ممکن برای $x$ را می‌شماریم :

1. $x$ صفر باشد : 1حالت
2. $x$ دو رقم داشته باشد : 20 = 1 حالت
3. $x$ چهار رقم داشته باشد: 21 حالت
4. $x$ شش رقم داشته باشد: 22 حالت
5. $x$ هشت رقم داشته باشد: 23 حالت
6. $x$ ده رقم داشته باشد: 24 حالت

و در کل 32 عدد ممکن برای $x$ خواهیم داشت.