פוסט הביטים שלי גרם לי לחשוב שאני לא מספיק עוצרת לבדוק כל מיני דרכים יצירתיות לפתור שאלות.
בדרך כלל אני מנסה להגיע לסיבוכיות הזמן/מקום האופטימלית, אבל תכל’ס זה יכול להיות ממש כיף לפעמים פשוט להתפרע, לצאת מהקופסא, ולחפש דרכים שהם אולי לא יעילות, אבל בהחלט מעניינות לעשות דברים.
חידת ה-5 ו-7 שעשיתי לפני כמה זמן הייתה ממש להיט והוכיחה כמה כיף זה יכול להיות (לכולן!), אז החלטתי לעשות עוד פוסט בסגנון, והפעם – 4 דרכים שונות לבדוק האם מספר הוא חזקה של 2.
שיטה ראשונה
בייצוג הבינארי של מספר שהוא חזקה של שתיים יהיה ביט אחד דלוק במקום של החזקה המתאימה, ואחריו אפסים.
לדוגמא –
x = 16 xb = 10000
אז כדי לבדוק אם מספר הוא חזקה של 2 אפשר לבדוק את מספר הביטים הדלוקים בייצוג הבינארי שלו.
def is_power_of_two_a(x):
x_bin = bin(x)[2:]
return x.count(‘1’) == 1
שיטה שנייה
מה עוד אני יודעת על חזקות של 2? אני יודעת שאם אני אתחיל מ-1 ואכפיל אותו שוב ושוב ב-2 אני אקבל סדרה של חזקות של 2, ואם x יהיה ביניהם סימן שהוא חזקה של 2, ואם אני אעבור את x בלי לעצור בו, אז הוא לא חזקה של 2.
def is_power_of_two_b(x):
power_of_two = 1
while power_of_two <= x:
if power_of_two == x:
return True
power_of_two *= 2
return False
שיטה שלישית
השיטה השלישית היא בדיוק מה שעשיתי מקודם, אבל בביטים, שזה אחר לגמרי!
במקום להכפיל ב-2 אני אעשה SHIFT של ביט אחד שמאלה (מה שמכפיל את המספר ב-2).
def is_power_of_two_c(x):
power_of_two = 1
while power_of_two < x:
power_of_two = power_of_two << 1
return power_of_two == x
שיטה רביעית
כן, כן, השיטה הקודמת הייתה קצת רמאות, אני יודעת, אז אני אנסה עכשיו לעשות משהו יצירתי קצת יותר, ובמקום להכפיל אני אחלק!
אני אתחיל מ-x ואבדוק את שארית החלוקה שלו ב-2. אם השארית היא לא אפס אז המספר לא זוגי (ומן הסתם לא חזקה של 2). את התוצאה אני גם אחלק ב-2 ושוב אבדוק את השארית, וכך אמשיך הלאה…
אם בנקודה כלשהי אני אגיע לתוצאה 1, סימן שאפשר להגיע מ-1 ל-x על ידי הכפלות חוזרות ב-2 – כלומר, x הוא חזקה של 2!
def is_power_of_two_d(x):
current_x = x
while current_x > 1:
if current_x % 2 == 1:
return False
current_x = current_x \2
return current_x == 1
הידד!
אלו היו כל הרעיונות שלי, אבל אני סומכת עליכן שתצליחו למצוא עוד מלא דרכים יצירתיות שלא חשבתי עליהן לבדוק האם מספר הוא חזקה של 2 🙂
שיטה חמישית
השיטה הזו הופיעה הרבה בתגובות, והיא ממש מגניבה, אז רציתי להוסיף אותה לפוסט עצמו.
בייצוג הבינארי מספר שהוא חזקה של 2 תמיד מיוצג כ-1 שאחריו רצף של n אפסים. כשמחסירים 1 ממספר שהוא חזקה של 2 מקבלים רצף של n אחדות בדיוק.
לדוגמא –
16 = 10000
16 - 1 = 15 = 1111
לכן, אם נבצע פעולת AND בין x ובין x-1, בעבור x שהוא חזקה של 2 תמיד נקבל 0, ובעבור x שאיננו חזקה של 2 תמיד נקבל מספר שונה מאפס.
על בסיס המסקנה הזו, אפשר להשתמש באלגוריתם הבא –
def is_power_of_two_d(x):
return x & (x-1) == 0
האחרונה היא כמו הראשונה (רק ששם השתמשת בספריה). הרי אם מצאת אחד וזה גדול מ2 אז יש עוד ביט.
שיטת אחרת זה להוריד אחד ולעשות and. אם זה חזקה של שתים כל הביטים צריכים להשתנות.
יפה.
לגבי השיטה הראשונה: למספרים בפייטון יש פונקציה בשם bit_length שמחזירה בדיוק את זה בלי להמיר את המספר למחרוזת.
אולי הזכרת במקום אחר, אבל יש את הטריק המגניב של and עם x-1.
תודה 🙂
עניין טכני לגמרי: ה־lt, ה־gt וה־amp יצאו בחוץ.
אבוי, איפה?
אפשר אולי לראות צילום מסך כי אני לא רואה את זה אצלי.
אותר ותוקן!
תודה רבה 🙂
יש קטע נהדר ב-HAKMEM שהסתובב בחוגי ההאקרים משנת 1972 (ואולי התגלגל קצת ל-Jargon File שנקרא גם New Hacker’s Dictionary), שמדבר על חזקות 2 ואיך אפשר להבין מתוכן על איזה מחשב התוכנה שלך רצה ואולי על איזה מחשב רץ היקום 🙂
Item 154 (Bill Gosper): The myth that any given programming language is machine independent is easily exploded by computing the sum of powers of 2. If the result loops with period = 1 with sign +, you are on a sign-magnitude machine. If the result loops with period = 1 at -1, you are on a twos-complement machine. If the result loops with period greater than 1, including the beginning, you are on a ones-complement machine. If the result loops with period greater than 1, not including the beginning, your machine isn’t binary — the pattern should tell you the base. If you run out of memory, you are on a string or bignum system. If arithmetic overflow is a fatal error, some fascist pig with a read-only mind is trying to enforce machine independence. But the very ability to trap overflow is machine dependent. By this strategy, consider the universe, or, more precisely, algebra: Let X = the sum of many powers of 2 = …111111 (base 2). Now add X to itself: X + X = …111110. Thus, 2X = X – 1, so X = -1. Therefore algebra is run on a machine (the universe) that is two’s-complement.
עוד פתרון נחמד אולי,
אפשר לייצר 32 או 64 bitmasks שיש לכל אחת מהן רק ביט אחד דולק.
ולעשות AND בין המספר שלנו לכל אחת מהן ולבדוק אם רק עבור פעולת and אחת
מקבלים תוצאה שהיא שונה מ 0.
זה אומנם לא הכי יעיל ומייצרים את המסיכות עם shift left שזה בפועל כמו לייצר
חזקות של 2 בכל צורה אחרת.
אבל אמרנו להתפרע :))
אהבתי מאוד את הפוסט!!