מספר הביטים הדולקים
שיעור 11 מתוך 17 בקורס מניפולציה על ביטים של Coddy.
ראשית, מה הם ביטים דלוקים?
הספרה '1' במספרים בינאריים נקראת ביט דלוק במונחי המחשב.
בשיעור הזה אנחנו רוצים לחשב את
מספר הביטים הדלוקים בצורה הבינארית של המספר הנתון.
לדוגמה, נניח שיש לנו את המספר (20)10 בבינארי (10100)2 , מספר הביטים הדלוקים ב-(20)10 הוא 2.
נסו לחשוב על גישה לפתרון. אולי תחשבו להמיר את המספר לצורתו הבינארית ולספור את מספר הספרות 1, בסדר, אבל מה לגבי מספרים גדולים? לא תוכלו לאחסן אותם בטיפוס הנתונים integer, אז איך נוכל לדעת מהו מספר הביטים הדלוקים במספרים גדולים? התשובה היא כמובן מניפולציה של ביטים!
- ראשית, נשתמש במשתנה מיקום ונקרא לו pos, כדי לדעת איזה ביט נמצא במיקום מסוים במספר הבינארי.
- לאחר מכן נבצע הזזה שמאלה pos פעמים על '1'.
- לאחר מכן פשוט נבצע פעולת AND עם המספר הנתון.
איך זה מועיל? נבין זאת בעזרת המספר (20)10 -
- עבור המיקום הראשון, pos=0.
20 & 1<<pos, 1<<pos=1 וביצוע פעולת AND על (10100)2 ועל (00001)2 נותן לנו אפס. - עבור המיקום השני, pos=1.
20 & 1<<pos, 1<<pos=(10)2 וביצוע פעולת AND על (10100)2 ועל (00010)2 נותן לנו אפס. - עבור המיקום השלישי, pos=2.
20 & 1<<pos, 1<<pos=(100)2 וביצוע פעולת AND על (10100)2 ועל (00100)2 נותן לנו אחד, כלומר הביט הדלוק הראשון שלנו. - עבור המיקום הרביעי, pos=2.
20 & 1<<pos, 1<<pos=(1000)2 וביצוע פעולת AND על (10100)2 ועל (01000)2 נותן לנו אפס. - עבור המיקום השלישי, pos=2.
20 & 1<<pos, 1<<pos=(10000)2 וביצוע פעולת AND על (10100)2 ועל (10000)2 נותן לנו אחד, כלומר הביט הדלוק השני.
כדי לספור את מספר הביטים הדלוקים נוכל להשתמש במשתנה מונה שיספור אותם. אבל אני מקווה שהדוגמה הזאת מבהירה לכם את האלגוריתם.
ובדרך הזאת נוכל לחשב בקלות את מספר הביטים הדלוקים בצורה הבינארית של מספר, בלי לחשוש לחרוג מטווח הערכים של טיפוס הנתונים int ב-C++.
אתגר
בינוניהשלימו את הפונקציה SetBits כדי להחזיר את מספר הביטים שהוגדרו במספר הנתון, באמצעות הגישה שלעיל.
נסו בעצמכם
#include <cmath>
int SetBits(int num) {
// כתבו כאן את הקוד
}כל השיעורים ביחידה מניפולציה על ביטים
2אלגוריתמים על ביטים
חזקה של 2מספר שמופיע מספר אי-זוגי של פעמיםמספר הביטים הדולקיםסיבוב הביטים של מספר Iסיבוב הביטים של מספר IIתרגלו בעצמכם: קומפיילר C++ אונליין