streamalism.org

1. סקירה כללית

במאמר זה נראה כיצד למצוא את ההספק הגדול ביותר של 2 שהוא פחות מהמספר הנתון.

לדוגמאות שלנו, ניקח את קלט הדגימה 9. 20 הוא 1, הקלט הכי פחות חוקי שעבורו אנו יכולים למצוא את העוצמה של 2 פחות מהקלט הנתון הוא 2. לפיכך רק נתייחס לתשומות הגדולות מ -1 כנכונות .

2. גישה נאיבית

נתחיל מ -20, שזה 1, ונתחיל המשך להכפיל את המספר ב -2 עד שנמצא מספר שהוא פחות מהקלט:

public long findLargestPowerOf2LessThanTheGivenNumber (קלט ארוך) {Assert.isTrue (קלט> 1, "קלט לא חוקי"); firstPowerOf2 ארוך = 1; ארוך nextPowerOf2 = 2; בעוד (nextPowerOf2 <קלט) {firstPowerOf2 = nextPowerOf2; nextPowerOf2 = nextPowerOf2 * 2; } להחזיר firstPowerOf2; }

בואו נבין את הקוד לדוגמא קֶלֶט = 9.

הערך ההתחלתי עבור firstPowerOf2 הוא 1 ו nextPowerOf2 הוא 2. כפי שאנו יכולים לראות, 2 <9 נכון, ואנחנו נכנסים לולאת ה- while.

לאיטרציה הראשונה, firstPowerOf2 הוא 2 ו nextPowerOf2 הוא 2 * 2 = 4. שוב 4 <9 אז בואו להמשיך את לולאת ה- while.

לאיתור השני, firstPowerOf2 הוא 4 ו nextPowerOf2 הוא 4 * 2 = 8. עכשיו 8 <9, בוא נמשיך.

לאיתור השלישי, firstPowerOf2 הוא 8 ו nextPowerOf2 הוא 8 * 2 = 16. תנאי ה- while 16 <9 אינו נכון, ולכן הוא פורץ מלולאת ה- while. 8 הוא הכוח הגדול ביותר מבין 2 שהוא פחות מ- 9.

בואו נערוך כמה בדיקות לאימות הקוד שלנו:

assertEquals (8, findPowerOf2LessThanTheGivenNumber (9)); assertEquals (16, findPowerOf2LessThanTheGivenNumber (32)); 

מורכבות הזמן של הפתרון שלנו היא O (log₂(N)). במקרה שלנו, איכלנו יומן₂(9) = 3 פעמים.

3. שימוש Math.log

בסיס יומן 2 ייתן כמה פעמים אנו יכולים לחלק מספר ב- 2 רקורסיבית במילים אחרות, עֵץ₂ של מספר נותן את העוצמה של 2. בואו נסתכל על כמה דוגמאות כדי להבין זאת.

עֵץ₂(8) = 3 והיכנס₂(16) = 4. באופן כללי, אנו יכולים לראות כי y = יומן₂x כאשר x = 2y.

מכאן שאם נמצא מספר שמתחלק ב -2, נגרע ממנו 1 כך שנמנע מתרחיש שבו המספר הוא כוח מושלם של 2.

Math.log הוא יומן₁₀. לחישוב יומן₂(x), נוכל להשתמש ביומן הנוסחאות₂(x) = יומן₁₀(x) / יומן₁₀(2)

בואו נכניס את זה לקוד:

public long findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2 (קלט ארוך) {Assert.isTrue (קלט> 1, "קלט לא חוקי"); טמפ 'ארוכה = קלט; אם (קלט% 2 == 0) {temp = קלט - 1; } כוח ארוך = (ארוך) (Math.log (temp) / Math.log (2)); תוצאה ארוכה = (ארוכה) Math.pow (2, כוח); תוצאת החזרה; }

בהנחה שקלט המדגם שלנו הוא 9, הערך ההתחלתי של טמפ ' הוא 9.

9% 2 זה 1, אז שלנו טמפ ' משתנה הוא 9.כאן אנו משתמשים בחלוקת מודולו, שתיתן את שארית 9/2.

כדי למצוא את היומן₂(9), אנחנו כן מתחברים₁₀(9) / יומן₁₀(2) = 0.95424 / 0.30103 ~= 3.

עכשיו ה תוֹצָאָה הוא 23 שזה 8.

בואו נאמת את הקוד שלנו:

assertEquals (8, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2 (9)); assertEquals (16, findLargestPowerOf2LessThanTheGivenNumberUsingLogBase2 (32));

במציאות, Math.pow נעשה את אותה האיטרציה שעשינו בגישה 1. לפיכך אנו יכולים לומר שגם לפיתרון זה, מורכבות הזמן היא O (יומן)₂(N)).

4. טכניקת Bitwise

לגישה זו נשתמש בטכניקת הסטה קצת חכמה. ראשית, נסתכל על הייצוגים הבינאריים בעוצמה של 2 בהתחשב בכך שיש לנו 4 סיביות לייצג את המספר

במבט מקרוב נוכל לראות שאנו יכולים חישב את העוצמה של 2 על ידי שמירת העברת הבתים למשך 1. כְּלוֹמַר. 22 הוא בתים משמרת שמאל למקומות 1 על 2 וכן הלאה.

בואו נקודד בטכניקת bitshift:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach (קלט ארוך) {Assert.isTrue (קלט> 1, "קלט לא חוקי"); תוצאה ארוכה = 1; כוח ארוך 2; עבור (ארוך i = 0; i <Long.BYTES * 8; i ++) {powerOf2 = 1 <= קלט) {הפסקה; } תוצאה = powerOf2; } להחזיר תוצאה; }

בקוד לעיל אנו משתמשים ארוך כסוג הנתונים שלנו, המשתמש ב- 8 בתים או 64 ביט. אז נחשב את ההספק של 2 עד 264. אנו משתמשים במפעיל משמרת הסיביות << כדי למצוא את הכוח של 2. עבור קלט המדגם 9 שלנו, לאחר האיטרציה הרביעית, הערך של powerOf2 = 16 ו- תוֹצָאָה = 8 שם אנו פורצים מהלולאה כ- 16> 9 the קֶלֶט.

בואו לבדוק אם הקוד שלנו עובד כצפוי:

assertEquals (8, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach (9)); assertEquals (16, findLargestPowerOf2LessThanTheGivenNumberUsingBitShiftApproach (32));

ה מורכבות הזמן הגרועה ביותר בגישה זו היא שוב O (יומן)₂(N)), בדומה למה שראינו לגישה הראשונה. עם זאת, גישה זו טובה יותר כ- פעולת משמרת סיביות יעילה יותר בהשוואה לכפל.

5. סיבית AND

לגישה הבאה שלנו, נשתמש בנוסחה זו 2n ו- 2n -1 = 0.

בואו נסתכל על כמה דוגמאות כדי להבין איך זה עובד.

הייצוג הבינארי של 4 הוא 0100, ו -3 הוא 0011.

בואו נעשה פעולה קצת חכמה על שני המספרים האלה. 0100 AND 0011 הוא 0000. אנחנו יכולים לומר את אותו הדבר בכל כוח של 2 ומספר פחות ממנו. ניקח 16 (24) ו- 15 המיוצגים כ- 1000, 0111 בהתאמה. שוב, אנו רואים כי ה- AND bitwise על שני אלה מביא ל- 0. אנו יכולים גם לומר שפעולת AND בכל מספר אחר מלבד 2 לא תביא ל- 0.

בואו נראה את הקוד לפתרון בעיה זו באמצעות AND ו- bitwise:

public long findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd (קלט ארוך) {Assert.isTrue (קלט> 1, "קלט לא חוקי"); תוצאה ארוכה = 1; עבור (ארוך i = קלט - 1; i> 1; i--) {אם ((i & (i - 1)) == 0) {תוצאה = i; לשבור; }} להחזיר תוצאה; }

בקוד לעיל אנו עוקפים מספרים פחות מהקלט שלנו. בכל פעם שאנחנו מוצאים את ה- bitwise AND של המספר והמספר 1 הוא אפס, אנחנו פורצים מהלולאה, כיוון שאנחנו יודעים שהמספר יהיה כוח של 2. במקרה זה לדוגמא שלנו קֶלֶט 9, אנחנו פורצים מהלולאה מתי אני = 8 ו אני – 1 = 7.

עכשיו, בואו נוודא כמה תרחישים:

assertEquals (8, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd (9)); assertEquals (16, findLargestPowerOf2LessThanTheGivenNumberUsingBitwiseAnd (32));

המקרה הכי גרוע מורכבות הזמן לגישה זו היא O (N / 2) כאשר הקלט הוא בעוצמה מדויקת 2. כפי שאנו רואים, זה לא הפיתרון היעיל ביותר, אך טוב לדעת טכניקה זו מכיוון שהיא יכולה להיות שימושית בעת התמודדות עם בעיות דומות.

6. מסקנה

ראינו גישות שונות למציאת הכוח הגדול ביותר של 2 שהוא פחות מהמספר הנתון. שמנו לב גם כיצד פעולות סיביות יכולות לפשט את החישובים במקרים מסוימים.

קוד המקור השלם עם בדיקות היחידה עבור מאמר זה ניתן למצוא באתר GitHub.