مبنای دو
مبنای دو چیست؟
به ما از بچگی یاد دادن وقتی میخوای یه چیزی رو بشمریم اول بیایم دونه دونه بشمریم به ده تا که رسید یه دسته ده تایی درست کنیم دوباره دونه دونه بریم تا برسیم به دسته ده تایی بعدی بعد هم که ده تا دسته ده تایی داشتیم یه دسته صد تایی درست کنیم و همینکارو ادامه بدیم با توان های بعدی ده. به این میگن مبنای ده که ما بلدیم.
اما ما کامپیوتری ها با مبنای دیگه ای خیلی از کارامون رو میکنیم مبنایی به اسم مبنای دو که ساز و کارش دقیقا مثل مبنای ده هست به این صورت که وقتی داریم میشمریم دوتا که شمردیم یه بسته دوتایی درست میکنیم. وقتی دوتا بسته دوتایی درست کردیم یه بسته 4 تایی درست میکنیم وقتی دوتا 4 تایی یه دونه 8 تایی درست میکنیم و الا اخر.
حالا بیایم ببینیم نمایش اعداد تو این مبنا ها چه طوریه. اول مبنای ده: مثلا عدد 1245 رو در نظر بگیرید این در واقع داره میگه من 5 تا بسته تکی دارم، 4 تا ده تایی، 2 تا 100 تایی و یک دونه 1000 تایی. پس در واقع عددمون رو اگر بخوایم به اصطلاح بسط بدیم به این صورته:
100 × 5 + 101 × 4 + 102 × 2 + 103 × 1 = 1245
حالا بیایم مبنای دو رو ببینیم: مثلا عدد 2(1011) یعنی یه دونه بسته تکی یه دونه بسته دوتایی 0 تا بسته 4 تایی و 1 دونه بسته 8 تایی اگر هم بسط مبنای دو این عدد رو بخوایم بنویسیم به این صورته:
20 × 1 + 21 × 1 + 22 × 0 + 23 × 1 = (11)10
عملیات های مبنای دو:
"یا"ی منطقی یا همون OR: به این صورته که بین دوتا عدد انجام میشه و طرز کارش اینطوریه که توی مبنای دو این دوتا عدد رو نگاه میکنه و هر جایگاه یا بیتی از این دوتا که حداقل در یکی از این اعداد یک بود جاش 1 میزاره وگرنه 0 میزاره حالا بیایم ببینیم منظور چیه:
مثلا
(101)2 OR (10011)2 = (10111)2
دقت کنید جایگاه اول توی هر دوعدد 1 بود پس عدد 1 خروجی گرفتیم برای جایگاه یا بیت دوم عدد اول 1 بود و عدد دوم 0 بود بازم 1 خروجی گرفتیم جایگاه سوم برای عدد دوم 1 بود و برای اولی 0 بود بازم یک خروجی گرفتیم جایگاه چهارم عدد دوم 3 رقمی بود اما ما در این عملیات اگر رقم کم بیاید 0 در نظر میگیریم پس جایگاه یا بیت 4 ام هر دوعدد 0 بود و 0 خروجی گرفتیم جایگاه پنجم برای عدد اول 1 بود و برای دومی 0 و 1 خروجی گرفتیم. میتونی این طوری یاد بگیری که هر بیتی که یا اولی یا دومی یا هر دو یک بودن رو یک خروجی میگیریم وگرنه 0.
"و"ی منطقی یا همون AND: این عملیات هم شبیه قبلیه یعنی بین دوتا عدده و هر بیت رو جداگونه برای هر دو بررسی میکنه ولی فرق این عملیات اینه که هر بیتی که جفت عددها 1 باشن رو 1 خروجی میده اگر حتی یکی از اعداد در اون بیت 0 بودند 0 خروجی میده.
مثلا بیایم همون دوتا عدد قبلی رو "و"ی منطقی بگیریم ببینیم چی میده بهمون:
(10011)2 AND (101)2 = (00001)2
خب همونطور که میبینید اون بیت هایی که حداقل یکی از اعداد توی اون بیت 0 بودند تبدیل به 0 شدند و بیت اول که جفت اعداد توی اون 1 بودند 1 خروجی داد. این عملیات هم میتونی اینطوری یاد بگیری که هر بیتی که توی عدد اول "و" عدد دوم 1 است رو یک خروجی میگیریم وگرنه 0.
XOR: این عملیات هم بین دو عدده و بیت به بیت بررسی میکنه عین قبلیا ولی تفاوتش تو خروجی اینه که اگر توی اون بیت دوتا عدد با هم فرق داشتن یعنی یکی 0 بود یکی 1 در این حالت اون بیت رو 1 خروجی میده و اگر با هم مساوی بودن توی اون بیت یعنی جفتی 0 یا جفتی 1 بودن 0 خروجی میده.
برای مثال همون دوتا عدد قبلی رو این دفعه XOR بگیریم ببینیم چی میده.
(10011)2 XOR (101)2 = (10110)2
بیت 2 و 5 ام فقط توی اولی 1 بودن توی دومی 0 بودن پس 1 خروجی گرفتیم و بیت 3 ام فقط توی دومی 1 بود توی اول 0 بود و بازم 1 خروجی گرفتیم اما بقیه بیت ها توی هر دو یکسان بودند پس 0 خروجی گرفتیم.
چند عدد 5 رقمی در مبنای دو، پالیندروم هستند؟
پالیندروم عددی است که از دو طرف به یک صورت خوانده بشود مانند 101.
اگر بیت 3 و 4 و 5 رو مشخص کنیم عدد یکتا در میاد.
پاسخ - 4
همون طور که تو راهنمایی گفتیم اگر اون 3 تا بیت رو مشخص کنیم چون عددمون پالیندرومه بیت 1 و 2 خودشون مشخص میشن.
بیت 5 ام از اونجایی که عددمون تو مبنای دو 5 رقمیه حتما 1 عه چون اگر 0 باشه عددمون 5 رقمی نمیشه دیگه.😐
بیت های 3 و 4 هم میتونن 0 باشن هم 1 پس واسه هر کدوم دو حالت داریم که طبق اصل ضرب واسه کل مساله 4 حالت داریم.
همه رشته های تولید شده از a و b را مرتب میکنیم؛ اول به ترتیب طول یعنی از طول کوچک به طول بزرگ و در طول های مساوی به ترتیب الفبایی به طور مثال 8 رشته اول به این صورت هستند:
a, b, aa, ab, ba, bb, aaa, aab
رشته 100 ام چیست؟
سعی کنید رشته هارو با اعداد تو مبنای دو متناظر کنی مثلا جای a ها 0 و به جای b ها 1.
پاسخ - baabab
جای a ها 0 و جای b ها 1 میذاریم و سمت چپ هرکدام از این اعداد به دست اومده یکدونه 1 میذاریم. به طور مثال 8 رشته اول به این صورت در می آیند.
10, 11, 100, 101, 110, 111, 1000, 1001
که اگر در مبنای ده این اعداد رو ببینیم به این صورتند:
2, 3, 4, 5, 6, 7, 8, 9
با این کاری که کردیم میفهمیم رشته n ام عددش n + 1 هست. پس اگر بخوایم رشته 100 ام رو پیدا کنیم اول باید ببینیم 101 توی مبنای دو به چه صورته. که به صورت مقابل هست (1100101)2
حال طبق متناظر سازی ای که کردیم اگر بخوایم به رشته اصلی برسیم باید 1 عه سمت چپ را برداریم اگر برداریم عددمان میشود 100101 که اگر دوباره بجای 1 ها b و بجای 0 ها a بذاریم میشود baabab.
چند عدد وجود دارند که در مبنای دو 10 رقمی هستند و AND انها با برعکس خودشان 0 شود.
بیت اخر با بیت اول خروجی تعیین میکنن. بیت دوم با بیت یکی مونده به اخر و الا اخر.
پاسخ - 81
اگر ما بیت i ام و 10 – i + 1 ام را نگاه کنیم از آنجایی که وقتی عدد را برعکس میکنیم این دو بیت زیر هم دیگه می ایند پس در فرایند AND گرفتن با هم بررسی میشوند و از آنجایی که قراره AND اینا 0 بشه پس این دو بیت مورد بررسی باید حداقل یک 0 بینشان باشد پس 3 حالت دارند. پس 53 حالت داریم اما نکته ای که وجود دارد این است که بیت اخر چون با یک عدد سر و کار داریم حتما 1 است پس برای 0 شدن AND باید بیت اول 0 باشد پس به استثناء بیت اول و اخر بقیه جفت ها 3 حالت دارند. درنتیجه در کل 34 حالت داریم.