هدف این است که با کُد نویسی بفهمیم که یک عدد آیا توان چندمی از عدد دو است یا خیر.
به طور مثال میخواهیم ورودی و خروجی های زیر را داشته باشیم:
N = 5 Output: false. N = 8 Output: true (23) N = 512 Output: true (29)
روش هایی که برای تشخیص پیشنهاد می شود:
- بررسی مقدار Log2 عدد (گرفتن لگاریتم پایه دو)
- بررسی باقی مانده تقسیم های متوالی بر دو
- تبدیل مبنای عدد به دو و بررسی بیت ها
روش Log2 :
لگاریتم پایه دو عدد را می گیریم و اگر مقدار لگاریتم عدد صحیحی بود می توانیم بگوییم عدد توانی از دو است.
کد جاوای آن به شکل زیر است:
public class PowerOf2LogMethod { public static void checkNumber(int n){ double x = Math.ceil(Math.log(n)/Math.log(2)); double y = Math.floor(Math.log(n)/Math.log(2)); if(x==y) System.out.println("Given number " + n + " is power of 2"); else System.out.println("Given number " + n + " is not power of 2"); } public static void main(String[] args) { int n = 6; checkNumber(n); n = 8; checkNumber(n); n = 24; checkNumber(n); n=512; checkNumber(n); } }
خروجی:
Given number 6 <strong>is not</strong> power of 2 Given number 8 <strong>is</strong> power of 2 Given number 24 <strong>is not</strong> power of 2 Given number 512 <strong>is</strong> power of 2
روش بررسی باقی مانده :
این راه حل به این صورت است که سعی می کنیم تقسیم های متوالی عدد بر دو را تا جایی که در نهایت به یک برسیم ادامه دهیم؛ اما اگر در این حین باقی مانده تقسیمی غیر صفر شد، به این معنی است که این عدد توان چندمی از دو نیست. پس اگر تمام تقسیم های متوالی باقی مانده صفر داشتند و در نهایت از عدد اولیه فقط فاکتور ۱ باقی ماند، عدد ما توانی از عدد دو است.
کد جاوای آن به شکل زیر است:
public class PowerOf2RemainderMethod { public static void checkNumber(int n){ boolean isPowOfTwo = true; int num = n; while(n>1){ if(n%2!=0) isPowOfTwo = false; n=n/2; } if(isPowOfTwo) System.out.println("Given number " + num + " is power of 2"); else System.out.println("Given number " + num + " is not power of 2"); } public static void main(String[] args) { int n = 6; checkNumber(n); n = 8; checkNumber(n); n = 24; checkNumber(n); n=512; checkNumber(n); } }
خروجی:
Given number 6 <strong>is not</strong> power of 2 Given number 8 <strong>is</strong> power of 2 Given number 24 <strong>is not</strong> power of 2 Given number 512 <strong>is</strong> power of 2
روش تبدیل مبنا به دو و بررسی بیتی :
هر عددی که توانی از دو باشد، در رشته بیتی معادل خود (در مبنای دو) تنها یک بیت ۱ دارد و مابقی همه صفر هستند (مثلاً معادل دودویی چهار برابر با ۱۰۰ و هشت برابر با ۱۰۰۰ و شانزده برابر با ۱۰۰۰۰ است).
پس ما ابتدا عددمان را به معادل دودویی آن تبدیل می کنیم و تعداد بیت های ۱ آن را می شماریم؛ که اگر این تعداد فقط یکی بود، عدد توانی از دو است.
کد جاوای آن به شکل زیر است:
public class PowerOfTwoBitMethod { public static void checkNumber(int n){ int countBits = countSetBits(n); if(countBits == 1) System.out.println("Given number " + n + " is power of 2"); else System.out.println("Given number " + n + " is not power of 2"); } public static int countSetBits(int number){ int count = 0; int x = number; while(number>0){ //check the last bit of number //if last bit is 1, increment the count count = count + (number & 1); //right shift the number number >>= 1; } return count; } public static void main(String[] args) { int n = 6; checkNumber(n); n = 8; checkNumber(n); n = 26; checkNumber(n); n=512; checkNumber(n); } }
خروجی:
Given number 6 <strong>is not</strong> power of 2 Given number 8 <strong>is</strong> power of 2 Given number 26 <strong>is not</strong> power of 2 Given number 512 <strong>is</strong> power of 2