חזקה של 2
שיעור 9 מתוך 17 בקורס מניפולציה על ביטים של Coddy.
אם התעסקת מספיק עם מספרים בינאריים, עד עכשיו ודאי שמת לב שלכל חזקה של 2 יש רק סיבית אחת דלוקה (סיבית דלוקה מתייחסת ל־'1'). לדוגמה: (2)10 = (10)2 , (4)10 = (100)2 , (8)10 = (1000)2 וכן הלאה.
בשיעור הזה נדון בבעיה:
מצאו אם מספר נתון הוא חזקה של 2 או לא, באמצעות מניפולציות על סיביות.
אוקיי! אז איך התצפית שלעיל תעזור לנו? בואו נגלה.
- נניח שנתון לנו (8)10 ואנחנו יודעים שהוא חזקה של 2.
- אם נחסר ממנו 1, נקבל (7)10, שהוא שווה ערך ל־(0111)2.
- אם נבצע פעולת AND ( & ) על 7 ו־8, נקבל 0.
- מעניין, נכון? בואו נבדוק מספר נוסף שהוא גם חזקה של 2. ניקח את (32)10, ששווה ערך ל־(100000)2, ונחסר ממנו 1, כלומר (31)10 = (011111)2. שוב נקבל 0!
- אז, כדי להכליל את זה, האם אפשר לומר שעבור מספר, נקרא לו x, כדי שיהיה חזקה של 2, ( x & (x-1) ) יהיה תמיד '0'?
ובאמצעות התצפית הזו אפשר לפתור בקלות את השאלה בלי להשתמש בספריית מתמטיקה או בפונקציית החזקה שלה, וגם בלי להשתמש בלולאה — פתרנו אותה בסיבוכיות זמן של O(1)! מגניב, נכון? כך מניפולציות על סיביות יכולות לעזור לנו לייעל את התוכניות שלנו במידה ניכרת, וגם להפוך את הקוד לפחות מסובך.
אתגר
קלבהינתן מספר, קבעו אם הוא זוגי או לא באמצעות מניפולציות על ביטים.
נסו בעצמכם
#include <iostream>
using namespace std;
bool IsPowerOf2(int num) {
// כתבו כאן קוד
}כל השיעורים ביחידה מניפולציה על ביטים
2אלגוריתמים על ביטים
חזקה של 2מספר שמופיע מספר אי-זוגי של פעמיםמספר הביטים הדולקיםסיבוב הביטים של מספר Iסיבוב הביטים של מספר IIתרגלו בעצמכם: קומפיילר C++ אונליין