חזקה של שתיים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
עריכה |
|||
שורה 2:
במתמטיקה, '''חזקה של שתיים''' היא מספר מהצורה 2<sup>n</sup>. כאשר ''n'' הוא מספר שלם, התוצאה של העלאת מספר ב[[חזקה (מתמטיקה)|חזקה]] כאשר המספר שתיים הוא הבסיס והשלם ''n'' הוא מעריך החזקה.
בהקשרים בהם רק מספרים שלמים נחשבים, ''n'' מוגבל למספרים אי-שליליים,
מכיוון ששתיים הוא מספר ה[[בסיס (אריתמטיקה)|בסיס]] של [[בסיס בינארי|מערכת הספירה הבינארית]], חזקות של שתיים הם דבר נפוץ ב[[מדעי המחשב]]. כאשר חזקה של שתיים תכתב בבינארית, היא תמיד תהיה בצורה {{משמאל לימין|100…000}} או {{משמאל לימין|0.00…001}}, בדיוק כמו חזקה של עשר ב[[עשרוני|מערכת העשרונית]].
== מספרי מרסן ==
ההתקדמות ההנדסית 1, 2, 4, 8, 16, 32, … (או, במערכת הספירה הבינארית, [[בסיס בינארי|במערכת הספירה הבינארית]], 1, 10, 100, 1000, 10000, 100000, … ) חשובה ב[[תורת המספרים]]. [[מספר ראשוני]] שהוא אחד פחות מחזקה של שתיים נקרא [[מספר מרסן]]. לדוגמה, המספר הראשוני [[31 (מספר)|31]] הוא מספר מרסן מכיוון שהוא אחד פחות מ-32 (2<sup>5</sup>).
באותו אופן, מספר ראשוני (כמו 257) שהוא אחד יותר מחזקה של שתיים נקרא [[מספר פרמה]].
==
ההצגה הבינארית של מספרים מאפשרים ליצור אלגוריתם מאוד מהיר שמחליט האם מספר [[מספר חיובי|חיובי]] [[מספר שלם|שלם]] נתון ''x'' הוא חזקה של שתיים: ▼
:המספר החיובי ''x'' הוא חזקה של שתיים ⇔ {{משמאל לימין|(''x'' & (''x'' - 1))}} שווה לאפס.▼
▲ההצגה הבינארית של מספרים מאפשרים
▲:המספר החיובי ''x'' הוא חזקה של שתיים ⇔ {{משמאל לימין|(''x'' & (''x'' - 1))}} שווה לאפס.
כאשר & הוא [[פעולה בוליאנית|פעולת AND על סיביות]]. אם ''x'' הוא 0, תוצאת האלגוריתם רומזת ש-0 הוא חזקה של שתיים, ולכן בדיקה זו עובדת רק כאשר ''x'' > 0.
בדומה לזה, האלגוריתם הבא מעגל את המספר הנתון ''x'' לחזקה קרובה של שתיים:
עבור כל שלם ''x'' וחזקה של שתיים , ''y'', נציב ''z'' = ''y'' - 1,
* {{משמאל לימין|''x'' & (!''z'')}} מעגל כלפי מטה,
| |||