سلام. عمل جمع و ضرب رو باید یک بیت یک بیت انجام بدید. در نظر بگیرید قراره بیت به بیت عدد A رو در عدد B جمع یا ضرب کنید.
برای جمع فرض کنید قصد دارید رقم iام از A رو با B جمع کنیم. باید i-1 رقم از سمت راست از B رو رد کنیم و از رقم iام از B شروع به جمع کنیم. هر چی ۱ دیدیم به صفر تبدیل کنیم و به چپ بریم. وقتی به اولین ۰ رسیدیم به ۱ تبدیل کنیم.
برای ضرب هم میدونیم ضرب عدد B (بصورت باینری) در $2^i$ هم ارز با قرار دادن iتا ۰ در سمت راست عدد B خواهد بود. کافیه یه کپی از B داشته باشیم و با توجه به تعداد ۱های عدد A عمل اضافه کردن ۰ و جمع رو انجام بدیم. (برای عمل جمع، عدد A حداقل باید دوتا ۱ داشته باشه) یا اینکه برای راحتی کار میشه هر مرحله یه واحد از A کم کرد و مقدار کپی شده از B رو با مقدار حاصل جمع، جمع کرد.

(۲۶ آذر ۱۳۹۳ ۰۲:۰۰ ب.ظ)Jooybari نوشته شده توسط:  سلام. عمل جمع و ضرب رو باید یک بیت یک بیت انجام بدید. در نظر بگیرید قراره بیت به بیت عدد A رو در عدد B جمع یا ضرب کنید.
برای جمع فرض کنید قصد دارید رقم iام از A رو با B جمع کنیم. باید i-1 رقم از سمت راست از B رو رد کنیم و از رقم iام از B شروع به جمع کنیم. هر چی ۱ دیدیم به صفر تبدیل کنیم و به چپ بریم. وقتی به اولین ۰ رسیدیم به ۱ تبدیل کنیم.
برای ضرب هم میدونیم ضرب عدد B (بصورت باینری) در $2^i$ هم ارز با قرار دادن iتا ۰ در سمت راست عدد B خواهد بود. کافیه یه کپی از B داشته باشیم و با توجه به تعداد ۱های عدد A عمل اضافه کردن ۰ و جمع رو انجام بدیم. (برای عمل جمع، عدد A حداقل باید دوتا ۱ داشته باشه) یا اینکه برای راحتی کار میشه هر مرحله یه واحد از A کم کرد و مقدار کپی شده از B رو با مقدار حاصل جمع، جمع کرد.

ممنون اما یکم گیج شدم، ممکنه لطف کنید و این الگوریتمی که گفتین رو با یک مثال توضیح بدین مثلا فرض کنیم A=0101 و B=1101 میشه برای اینها دو گامش رو برید
برای همین مثال بالا که زدم من بر اساس صحبت های شما اینطور برداشت کردم که
A و B روی tape هستند و مامیخواهیم جمع کنیم A اول اومده بعد هم B اومده و بایک علامت هم جدا شدند از هم.خوب حالا از ابتدای رشته ی A شروع میکنم و میرم تا به انتهاش برسم از انتهای رشته شروع میکنم به جمع کردم بیت انتهای رشته رو میگیرم بیت یکم از رشته ی A و میرم انتهای رشته ی B که i-1 امین بیتش با احتساب i=1 برابر با صفر میشه از بیت i ام رشته B شروع میکنم و هرچی یک دیدم سر راهم تبدیل به ۰ میکنم و به اولین صفری که رسیدم اون رو تبدیل به یک میکنم و باقی رشته خودش گذاشته میشه که برای مثال ما میشه ۱۱۱۰
درگام دوم همین عمل رو تکرار میکنیم این دفعه برای صفر انتهایی دیگه این عمل رو تکرار نمیکنیم چرا که از i-1 امی باید شروع کنیم که مرحله دوم میشه بیت دوم.
خوب حالا این روند ادامه داره تا تمام بشه رشته
برای من چند تا سوال ایجاد شده یکی اینکه روی رشته B که نمینویسیم حاصل جمع رو نه؟ چون برای جمع بیت بعدی لازم دارم خود رشته اصلی رو
و یک سوال دیگه طول رشته مون هرچی بود نباید یک خونه صفر خالی سمت چپش بگذاریم برای carry؟ چون الان همین مثال کری برابر با یک میشه و خوب اگر یک خونه با مقدار صفر نباشه تغییر میکنه جواب.

(۲۶ آذر ۱۳۹۳ ۰۶:۱۷ ب.ظ)m-kafiyan نوشته شده توسط:  ممنون اما یکم گیج شدم، ممکنه لطف کنید و این الگوریتمی که گفتین رو با یک مثال توضیح بدین مثلا فرض کنیم A=0101 و B=1101 میشه برای اینها دو گامش رو برید

برای جمع:
به ازای ۱ سمت راست از A که به B اضافه میشه، مقدار B به ۱۱۱۰ تغییر میکنه. اولین بیت B برابر ۱ بود که به ۰ تغییر میکنه دومین بیت هم ۰ بود که به ۱ تغییر میکنه. چون به صفر رسیدیم عمل جمع این بیت تموم شده.
به ازای دومین ۱ از A (بیت سوم) باید روی بیت سوم از B بریم و جمع رو انجام بدیم. مقدار حاصل از ۱۱۱۰ به ۱۰۰۱۰ تغییر میکنه. بیت سوم و چهارم از B از ۱ به ۰ تغییر میکنن و بیت پنجم (وجود نداره و ما ۰ درنظر میگیریم) به ۱ تغییر میکنه و عمل جمع بیت تموم میشه.
چون مقدار A هیچ ۱ دیگه ای نداره عمل جمع تمومه.

برای ضرب:
مقدار حاصل از شیفت B به ازای اولین بیت ۱ از A:
۱۱۰۱
مقدار حاصل از شیفت B به ازای دومین بیت ۱ از A:
۱۱۰۱۰۰
چون دو مقدار حاصل شد باهم جمع میکنیم. حاصل میشه ۱۰۰۰۰۰۱
مقدار A دیگه ۱ نداره. پس نیاز به عمل شیفت و جمع دیگه ای نیست.

(۲۶ آذر ۱۳۹۳ ۰۶:۵۳ ب.ظ)Jooybari نوشته شده توسط:  برای جمع:
به ازای ۱ سمت راست از A که به B اضافه میشه، مقدار B به ۱۱۱۰ تغییر میکنه. اولین بیت B برابر ۱ بود که به ۰ تغییر میکنه دومین بیت هم ۰ بود که به ۱ تغییر میکنه. چون به صفر رسیدیم عمل جمع این بیت تموم شده.
به ازای دومین ۱ از A (بیت سوم) باید روی بیت سوم از B بریم و جمع رو انجام بدیم. مقدار حاصل از ۱۱۱۰ به ۱۰۰۱۰ تغییر میکنه. بیت سوم و چهارم از B از ۱ به ۰ تغییر میکنن و بیت پنجم (وجود نداره و ما ۰ درنظر میگیریم) به ۱ تغییر میکنه و عمل جمع بیت تموم میشه.
چون مقدار A هیچ ۱ دیگه ای نداره عمل جمع تمومه.

برای ضرب:
مقدار حاصل از شیفت B به ازای اولین بیت ۱ از A:
۱۱۰۱
مقدار حاصل از شیفت B به ازای دومین بیت ۱ از A:
۱۱۰۱۰۰
چون دو مقدار حاصل شد باهم جمع میکنیم. حاصل میشه ۱۰۰۰۰۰۱
مقدار A دیگه ۱ نداره. پس نیاز به عمل شیفت و جمع دیگه ای نیست.

ممنون توضیحاتتون بسیار واضح و خوب بود.