אופרטור XOR
שיעור 6 מתוך 17 בקורס מניפולציה על ביטים של Coddy.
אופרטור XOR ( ^ )
פעולת XOR ברמת הסיביות מקבלת שתי תבניות סיביות באורך שווה. אם אורכן אינו שווה, פשוט הוסיפו אפסים לפני הסיבית המשמעותית ביותר (MSB) של תבנית הסיביות הקצרה יותר. אם שתי הסיביות במיקום המושווה בתבניות הסיביות שוות, הסיבית בתבנית הסיביות המתקבלת תהיה 0, אחרת 1.
הסמל '^' משמש לייצוג פעולת XOR.
כשמדברים במונחים מתמטיים, משתמשים ב-'⊕' כדי לייצג XOR. לכן, ייתכן שתיתקלו גם בסימן הזה בחלק מהשאלות. עכשיו נכין טבלה כדי לראות מה אופרטור XOR מחזיר בכל הצירופים האפשריים של שתי סיביות.
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| x ^ y | 0 | 1 | 1 | 0 |
ניקח דוגמה כדי להבין טוב יותר את הפעולה—
בדוגמה שלמעלה ביצענו פעולת XOR על (11)10 ו-(2)10 , והתוצאה הייתה (9)10. פשוט כתבנו את המספרים האלה בצורה הבינארית שלהם, השווינו בין שתי הסיביות ופעלנו לפי ההגדרה של פעולת XOR שלמעלה.
שימוש:
int a = 1;
int b = 0;
>> a ^ b
OUTPUT: 1כעת, ל-XOR יש כמה תכונות חשובות שיקצרו את הזמן שיידרש לכם לפתור שאלות הקשורות ל-XOR, אם אינכם מכירים אותן.
כמה תכונות חשובות של XOR
- x ⊕ 0 = x - אם תבצעו XOR בין מספר לאפס, תקבלו את אותו המספר.
- x ⊕ x = 0 - אם תבצעו XOR בין מספר לעצמו, תקבלו אפס.
- ניקח שני מספרים, x ו-y. נניח ש-x ⊕ y = z. אז גם x ⊕ z = y וגם y ⊕ z = x הן שוויונות נכונים.
אתגר
בינונישון אוהב ללבוש גרביים ולהחזיק בארון שלו גרביים מסוגננות שונות. הוא שומר את הגרביים שלו עם מספרים כתובים עליהן. לדוגמה, (1,1), (10, 10) מייצגים שני זוגות גרביים. למרבה הצער, יום אחד חתול פורץ לארון שלו ולוקח גרב. הגרביים שנמצאות בארון ניתנות לך כמערך. השלימו את הפונקציה MissingSock כדי למצוא איזו גרב החתול לקח.
לדוגמה,
בארון היו במקור 6 גרביים: 1, 1, 2, 3, 3, 2,
- 2 גרביים עם המספר
1 - 2 גרביים עם המספר
2 - 2 גרביים עם המספר
3
החתול הגיע וגנב גרב אחת שמספרה 1. הקלט כעת הוא: 1, 2, 3, 3, 2, כי חסרה גרב אחת שמספרה 1. האתגר הוא למצוא את הגרב החסרה (הפלט צריך להיות 1, כי זו הגרב החסרה).
נסו בעצמכם
#include <iostream>
#include <vector>
using namespace std;
int MissingSock(vector<int> socks) {
// כתבו כאן את הקוד
}כל השיעורים ביחידה מניפולציה על ביטים
תרגלו בעצמכם: קומפיילר C++ אונליין