Power of Two
נתון לך מספר שלם n. החזר true אם n הוא חזקה של שתיים, כלומר n = 2^k עבור מספר שלם אי־שלילי כלשהו k ≥ 0, ואחרת החזר false. לכן 1, 2, 4 ו־8 נחשבים, ואילו 0, 6 וכל מספר שלילי אינם נחשבים.
פונקציה
- ninteger
- המספר השלם לבדיקה, שעשוי להיות אפס או שלילי
- מחזירהboolean
- אמת אם n שווה ל־2^k עבור k ≥ 0, אחרת שקר
אילוצים
-231 ≤ n ≤ 231-1
דוגמאות
- קלט
- n = 16
- פלט
- true
- הסבר
- 16 = 2 × 2 × 2 × 2 = 2^4. בייצוג בינארי הוא
10000, ביט 1 יחיד.
- קלט
- n = 24
- פלט
- false
- הסבר
- 24 = 8 × 3. חלוקה לשניים נותנת 12, 6 ואז 3, שהוא אי-זוגי אך אינו 1. בייצוג בינארי 24 הוא
11000, עם שני ביטים של 1.
- קלט
- n = 1
- פלט
- true
- הסבר
- 1 = 2^0, לכן זו חזקה של 2. לצורה הבינארית שלה
1יש בדיוק ביט 1 אחד.
שאלת המשך
בעזרת אותן טריקים של ביטים, האם תוכל לבדוק אם n הוא חזקה של ארבע בלי להשתמש בלולאה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כתבו כמה חזקות של שתיים בבינארי:
1,10,100,1000. מה משותף לכולן שאין ב־6 (110)?בחזקה של 2 יש בדיוק ביט 1 אחד. השווה את
nל־n-1בייצוג בינארי: חיסור 1 הופך את ביט ה־1 הנמוך ביותר ל־0 ואת כל ביטי ה־0 שמתחתיו ל־1.לכן
nהוא חזקה של שתיים בדיוק כאשר הוא חיובי, ופעולת AND שלו עםn-1נותנת 0. בדוק את הסימן לפני הביטים, כי 0 ומספרים שליליים לעולם אינם חזקות של שתיים.
פתרון
לחזקה של 2 יש צורה קבועה בבינארי: סיבית 1 אחת ואחריה אפסים, כמו 10000 עבור 16. אפשר לוודא את הצורה הזאת על ידי חלוקה של n ב-2 עד שהוא הופך לאי-זוגי, תהליך שאורך עד 31 צעדים. לחלופין, אפשר לוודא זאת בצעד אחד באמצעות n & (n-1), שמנקה את סיבית ה-1 הנמוכה ביותר ומשאיר 0 רק כשהסיבית הזאת הייתה היחידה. בשתי הגרסאות, בדיקת הסימן מתבצעת תחילה, כי אפס ומספרים שליליים שוברים את הקוד המתבקש.
חלקו ב־2 כל עוד המספר זוגי
האינטואיציה
אם n = 2^k, אפשר לחלק אותו ב־2 בדיוק k פעמים ולהגיע ל־1, וכל הערכים בדרך זוגיים. אם ל־n יש גורם אי־זוגי גדול מ־1, החלוקה לחצי נעצרת במספר אי־זוגי שאינו 1. עבור 16: 16, 8, 4, 2, 1, ולכן התשובה היא true. עבור 24: 24, 12, 6, 3, ו־3 הוא אי־זוגי אך אינו 1, ולכן התשובה היא false.
החזר false עבור n ≤ 0 לפני הלולאה. שום חזקה של 2 אינה אפס או שלילית, והלולאה לעולם לא תסתיים ב־0, כי 0 הוא זוגי ומחצית מ־0 היא עדיין 0.
בכל שלב n מתחלק לחצי, לכן קלט של 32 סיביות דורש לכל היותר 31 שלבים: זמן O(log n) ומקום O(1).
אלגוריתם
- אם
n ≤ 0, יש להחזיר false. - כל עוד
nזוגי, יש לחלק אותו ב-2. - יש להחזיר האם
nהוא כעת 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1נקה את הסיבית הדלוקה הנמוכה ביותר באמצעות n & (n-1)
האינטואיציה
כותבים חזקה של 2 בבינארי, ומקבלים 1 יחיד ואחריו אפסים: 16 הוא 10000. חיסור 1 הופך את ה־1 הזה ל־0 ואת כל האפסים שמתחתיו ל־1: 15 הוא 01111. אין לשני המספרים ביט 1 משותף, ולכן 16 & 15 הוא 0.
לכל מספר חיובי אחר יש לפחות שני ביטים שערכם 1. חיסור 1 משנה רק את ביט ה־1 הנמוך ביותר ואת האפסים שמתחתיו, ולכן כל ביט 1 גבוה יותר מופיע בשני המספרים והתוצאה של AND אינה 0. עבור 24, שהוא 11000, מקבלים 23 = 10111, ו־24 & 23 הוא 10000, שערכו 16.
בודקים קודם n > 0. 0 & -1 הוא 0, ובאריתמטיקה של 32 ביטים -2^31 הוא ביט 1 יחיד ואחריו 31 אפסים, כך שבדיקת AND לבדה הייתה מזהה את שניהם כחזקות של 2. הבדיקה כולה כוללת השוואה אחת, חיסור אחד ו־AND אחד: זמן ומקום O(1). ל־Lua 5.1 אין אופרטור AND, לכן קוד Lua בונה את תוצאת ה־AND ביט אחר ביט, עד 31 צעדים עבור n של 32 ביטים; הבדיקה זהה.
אלגוריתם
- אם
n ≤ 0, החזר false. - חשב את
n & (n-1), כלומר אתnלאחר איפוס סיבית ה־1 הנמוכה ביותר שלו. - החזר האם התוצאה היא 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
מלכודות ומקרי קצה
בדיקת הביט היא שורה אחת, ורוב הטעויות קשורות לקלטים שהיא לא תוכננה להתמודד איתם.
- דילוג על בדיקת הסימן.
0 & (0-1)הוא 0, ולכן 0 עובר את בדיקת ה-AND. במספרים שלמים בני 32 ביט, גם-2^31עובר, כי הייצוג הבינארי שלו הוא ביט 1 יחיד. שניהם חייבים להחזיר false. - הרצת לולאת החלוקה לחצי על 0. אפס הוא זוגי, וחלוקה שלו לחצי נותנת שוב 0, ולכן הלולאה לעולם לא מסתיימת.
- השמטת הסוגריים. ל-
==קדימות גבוהה יותר מאשר ל-&, ולכן ב-C, ב-C++ וב-JavaScript הביטויn & n - 1 == 0נקרא כך:n & ((n - 1) == 0), ומחזיר תשובה שגויה בלי להציג שגיאה; Java ו-C# דוחות אותו כשגיאת טיפוס. כתבו(n & (n - 1)) == 0. - שימוש בלוגריתמים. בדיוק כפול,
log(536870912) / log(2)מתקבל כ-29.000000000000004 במקום 29, ולכן בדיקת מספר שלם קובעת ש-2^29הוא false.
שאלות נפוצות3
איך בודקים אם מספר הוא חזקה של שתיים?
החזר true כאשר n > 0 ו-n & (n-1) שווה ל-0. לחזקה של שתיים יש בדיוק ביט 1 אחד, והחסרת 1 מאפסת אותו ומדליקה רק את הביטים שמתחתיו, ולכן תוצאת פעולת AND היא 0. בלי פעולות על ביטים, חלק את n ב-2 כל עוד הוא זוגי ובדוק שבסוף מתקבל 1.
למה n & (n-1) מאפס את הביט הדלוק הנמוך ביותר?
חיסור 1 לוקח הלוואה מהביט 1 הנמוך ביותר: הביט הזה הופך ל־0 וכל 0 שמתחתיו הופך ל־1, בעוד שהביטים הגבוהים יותר נשארים ללא שינוי. ביצוע AND עם הערך המקורי משאיר רק את הביטים שמוגדרים ב־1 בשניהם, ואלה בדיוק הביטים הגבוהים יותר. בחזקה של 2 אין ביטים גבוהים יותר, ולכן התוצאה היא 0.
מהי סיבוכיות הזמן של חזקה של שתיים?
הבדיקה n & (n-1) רצה בזמן ובמרחב O(1): השוואה אחת, חיסור אחד ופעולת AND אחת. לולאת החלוקה לחצי רצה בזמן O(log n), לכל היותר 31 צעדים עבור מספר שלם בן 32 סיביות.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def isPowerOfTwo(n):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
n = 16
הפלט הצפוי
true