اسکریپت شناسایی توان‌های عدد ۲ در پایتون

شاید در زمان برنامه‌نویسی برای شما نیز پیش‌آمده باشد که خواسته باشید ببینید آیا یک عدد توانی از 2 است یا خیر؟ به‌ویژه با توجه به اینکه در منطق باینری توان‌های 2 از جایگاه ویژه‌ای برخوردار هستند این مسئله اهمیت بیشتری پیدا می‌کند. می‌توان در زبان پایتون یک الگوریتم بیتی و تکرارشونده برای حل این مسئله نوشت.

الگوریتم با منطق بیتی

برای این‌که الگوریتمی که می‌نویسیم بیتی باشد باید از عملگر افسانه‌ای AND (&) استفاده کنیم. راه‌حل این مسئله بر اساس این خصوصیت منحصربه‌فرد طراحی‌ شده است که همه توان‌های 2 در مجموعه ارقام دودویی خود، تنها یک مقدار 1 دارند و باقی ارقامشان صفر است. بنابراین راه‌حل نخست این است که بررسی کنیم اگر این تک‌بیت (bit) را حذف کنیم عبارت ما برابر صفر می‌شود یا خیر. اگر چنین شد یعنی توان 2 است. البته یک استثنا وجود دارد و آن عدد صفر است. اگر عدد صفر به اسکریپت زیر داده شود مشاهده می‌کنید علی‌رغم این‌که صفر توانی از 2 نیست ولی مقدار بازگشتی اسکریپت مثبت خواهد بود. برای حذف این حالت استثنایی باید مطمئن شویم که عدد ورودی صفر نیست.

فیلم آموزش برنامه نویسی پایتون + مثال های عملی در Python در فرادرس

کلیک کنید

تابع مربوطه به شکل زیر است:

# Bitwise version
def powTwoBit(number):
return (number & (number-1) == 0) and (number!= 0)

الگوریتم با منطق تکرار‌ شونده

درک راه‌حل دوم در صورتی‌که چندان به عملگرهای بیتی علاقه‌مند نباشید آسان‌تر خواهد بود، چون بر اساس تعریف یک حلقه معمولی بر روی یک ویژگی همه توان‌های 2 عمل می‌کند. ویژگی مذکور این است که همه توان‌های 2 زمانی که بر 2 تقسیم شوند باقیمانده‌ای نخواهند داشت. بنابراین در این راه‌حل یک حلقه تعریف می‌کنیم و در آن عدد مربوطه را بر 2 تقسیم می‌کنیم تا اینکه به عددی غیر از 1 برسیم در این صورت عدد توانی از 2 است. اگر در هر یک از مراحل باقیمانده‌ای ایجاد شود در این صورت مشخص می‌شود که این عدد توانی از 2 نیست. البته باید این قاعده را در نظر گرفت که عدد می‌بایست یک عدد مثبت باشد.

#Iterative version
def powTwoIter(number):
isPowOfTwo=True;
while (number!= 1 and number > 0):
if(number%2):
# can do return here as well
isPowOfTwo = False
number=number/2
return isPowOfTwo and (number > 0)

بنابراین در زبان برنامه‌نویسی پایتون دو راه‌حل برای فهمیدن اینکه عددی توان 2 است یا خیر وجود دارد. البته می‌توان راه‌حل‌های بسیار زیاد دیگری نیز برای این مسئله نوشت. برای نمونه می‌توان آرایه‌ای از مقادیر توان‌های 2 ایجاد کرد که از کمترین به بزرگ‌ترین مرتب‌ شده‌اند و با استفاده از جستجوی دودویی مشخص کرد که عدد مربوطه در این آرایه وجود دارد یا خیر.

انتخاب این‌که از چه راه‌حلی استفاده کنید کاملاً به نظر شما بستگی دارد. لطفاً نظرتان را در مورد این راه‌حل‌ها در بخش نظرات مطرح کنید.