חזקה של שתיים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

חזקה של שתיים היא מספר טבעי מהצורה . כלומר מספר המתקבל מהכפלת 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.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא חזקה של שתיים בוויקישיתוף