חזקה של שתיים

חזקה של שתיים היא מספר טבעי מהצורה $2^{n}$. כלומר מספר המתקבל מהכפלת 2 בעצמו n פעמים.

את החזקות של שתיים ניתן לחשב באופן רקורסיבי, כאשר המספר הראשון הוא $2^{0}=1$ והחזקה הבאה מתקבלת מחיבור החזקה הקודמת לעצמה.

לפי המשפט היסודי של האריתמטיקה, מספר הוא חזקת שתיים אם ורק אם אין לו אף גורם ראשוני אי-זוגי.

כיוון ש-2 הוא מספר הבסיס של מערכת הספירה הבינארית, חזקות של שתיים נפוצות במדעי המחשב. כאשר בכתיב בינארי חזקה של שתיים היא תמיד מהצורה 100…000, בדיוק כמו חזקה של עשר במערכת העשרונית.

סדרת החזקות של שתיים

הסדרה ההנדסית 1, 2, 4, 8, 16, 32, … (או, במערכת הספירה הבינארית, 1, 10, 100, 1000, 10000, 100000, … ) שאיבריה הם החזקות של 2 חשובה בתורת המספרים. סכום n האיברים הראשונים בסדרה, השווה ל-$1+2+\ldots +2^{n-1}=2^{n}-1$, נקרא מספר מרסן. מספרים אלו, בעיקר אלו מהם שהם מספרים ראשוניים, נחקרו עוד מהעת העתיקה והם קשורים למספרים משוכללים.

מספר ראשוני שהוא אחד יותר מחזקה של שתיים (למשל 257) נקרא ראשוני פרמה. ראשוני כזה הוא בהכרח מהצורה $2^{2^{n}}+1$.

מימוש מהיר של פעולות בחזקות של שתיים

ההצגה הבינארית של מספרים מאפשרת לבדוק במהירות האם מספר חיובי שלם נתון 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 המשבצות הוא $2^{64}-1=18,446,744,073,709,551,615$).

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

קישורים חיצוניים

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

• סדרת החזקות של 2 באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים