חזקה של שתיים
חזקה של שתיים היא מספר טבעי מהצורה . כלומר מספר המתקבל מהכפלת 2 בעצמו n פעמים.
את החזקות של שתיים ניתן לחשב באופן רקורסיבי, כאשר המספר הראשון הוא והחזקה הבאה מתקבלת מחיבור החזקה הקודמת לעצמה.
לפי המשפט היסודי של האריתמטיקה, מספר הוא חזקת שתיים אם ורק אם אין לו אף גורם ראשוני אי-זוגי.
כיוון ש-2 הוא מספר הבסיס של מערכת הספירה הבינארית, חזקות של שתיים נפוצות במדעי המחשב. כאשר בכתיב בינארי חזקה של שתיים היא תמיד מהצורה 100…000, בדיוק כמו חזקה של עשר במערכת העשרונית.
סדרת החזקות של שתיים
הסדרה ההנדסית 1, 2, 4, 8, 16, 32, … (או, במערכת הספירה הבינארית, 1, 10, 100, 1000, 10000, 100000, … ) שאיבריה הם החזקות של 2 חשובה בתורת המספרים. סכום n האיברים הראשונים בסדרה, השווה ל-, נקרא מספר מרסן. מספרים אלו, בעיקר אלו מהם שהם מספרים ראשוניים, נחקרו עוד מהעת העתיקה והם קשורים למספרים משוכללים.
מספר ראשוני שהוא אחד יותר מחזקה של שתיים (למשל 257) נקרא ראשוני פרמה. ראשוני כזה הוא בהכרח מהצורה .
מימוש מהיר של פעולות בחזקות של שתיים
ההצגה הבינארית של מספרים מאפשרת לבדוק במהירות האם מספר חיובי שלם נתון x הוא חזקה של שתיים:
- המספר החיובי x הוא חזקה של שתיים ⇔ (x & (x - 1)) שווה לאפס.
כאשר & הוא פעולת AND על סיביות. אם x הוא 0, תוצאת האלגוריתם רומזת ש-0 הוא חזקה של שתיים, ולכן בדיקה זו עובדת רק כאשר x > 0.
בדומה לזה, האלגוריתם הבא מעגל את המספר הנתון x לחזקה קרובה של שתיים: עבור כל שלם x וחזקה של שתיים, y, נציב z = y - 1,
- x & (!z) מעגל כלפי מטה,
- (x + z) & (!z) מעגל כלפי מעלה,
- (x + y / 2) & (!z) מעגל לחזקה הקרובה ביותר.
החזקות הראשונות של שתיים
סדרה A000079, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים
20 | = | 1 | 216 | = | 65,536 | 232 | = | 4,294,967,296 | 248 | = | 281,474,976,710,656 | |||
21 | = | 2 | 217 | = | 131,072 | 233 | = | 8,589,934,592 | 249 | = | 562,949,953,421,312 | |||
22 | = | 4 | 218 | = | 262,144 | 234 | = | 17,179,869,184 | 250 | = | 1,125,899,906,842,624 | |||
23 | = | 8 | 219 | = | 524,288 | 235 | = | 34,359,738,368 | 251 | = | 2,251,799,813,685,248 | |||
24 | = | 16 | 220 | = | 1,048,576 | 236 | = | 68,719,476,736 | 252 | = | 4,503,599,627,370,496 | |||
25 | = | 32 | 221 | = | 2,097,152 | 237 | = | 137,438,953,472 | 253 | = | 9,007,199,254,740,992 | |||
26 | = | 64 | 222 | = | 4,194,304 | 238 | = | 274,877,906,944 | 254 | = | 18,014,398,509,481,984 | |||
27 | = | 128 | 223 | = | 8,388,608 | 239 | = | 549,755,813,888 | 255 | = | 36,028,797,018,963,968 | |||
28 | = | 256 | 224 | = | 16,777,216 | 240 | = | 1,099,511,627,776 | 256 | = | 72,057,594,037,927,936 | |||
29 | = | 512 | 225 | = | 33,554,432 | 241 | = | 2,199,023,255,552 | 257 | = | 144,115,188,075,855,872 | |||
210 | = | 1,024 | 226 | = | 67,108,864 | 242 | = | 4,398,046,511,104 | 258 | = | 288,230,376,151,711,744 | |||
211 | = | 2,048 | 227 | = | 134,217,728 | 243 | = | 8,796,093,022,208 | 259 | = | 576,460,752,303,423,488 | |||
212 | = | 4,096 | 228 | = | 268,435,456 | 244 | = | 17,592,186,044,416 | 260 | = | 1,152,921,504,606,846,976 | |||
213 | = | 8,192 | 229 | = | 536,870,912 | 245 | = | 35,184,372,088,832 | 261 | = | 2,305,843,009,213,693,952 | |||
214 | = | 16,384 | 230 | = | 1,073,741,824 | 246 | = | 70,368,744,177,664 | 262 | = | 4,611,686,018,427,387,904 | |||
215 | = | 32,768 | 231 | = | 2,147,483,648 | 247 | = | 140,737,488,355,328 | 263 | = | 9,223,372,036,854,775,808 |
אגדות על חזקות של שתיים
האגדה על המצאת השחמט מספרת שהמלך הציע לממציא לבחור איזה פרס הוא רוצה בתמורה להמצאתו הנפלאה. הממציא אמר שהוא מבקש גרגר חיטה במשבצת הראשונה של לוח השחמט, 2 גרגרים בשנייה, 4 גרגרים בשלישית, 8 ברביעית וכן הלאה, בטור הנדסי. המשימה נראתה בעיני המלך כעניין של מה בכך, והוא פקד על משרתיו למלאה, אך מהר מאוד גילה שכל מחסני התבואה בממלכה התרוקנו, בזמן שמילוי משאלתו של הממציא רחוק מלהתגשם (כבר במשבצת ה-32 נדרשו יותר משני מיליארד גרגרים, ומספר הגרגרים שידרשו כנגד 64 המשבצות הוא ).
לפי האגדה שממציא המשחק של מגדלי האנוי צירף לו, כוהנים ברהמינים צריכים להעביר 64 דיסקיות ממוט אחד לאחר, וכשיסיימו יגיע סוף העולם. גם כאן, מספר הצעדים שידרשו הוא 264-1.
קישורים חיצוניים
- סדרת החזקות של 2, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.
29892894חזקה של שתיים