נציע פתרון לבעיה שהוצעה בפוסט הקודם.
המפתח לפתרון הבעיה הוא עבודה עם XOR.
למי שלא יודע את תכונות ה-XOR מוזמן לקרוא כאן.
בקצרה, פעולת ה-XOR על שני מספרים תתן תוצאה של מספר המורכב מביטים בהם מופיע "01" או "10" בשני המספרים.
לדוגמא:
ולכן XOR של המספר 3 ו- 5 ייתן את התוצאה 6.
אנחנו נשתמש בתכונות ה-XOR כדי לפתור את הבעיה:
המפתח לפתרון הבעיה הוא עבודה עם XOR.
למי שלא יודע את תכונות ה-XOR מוזמן לקרוא כאן.
בקצרה, פעולת ה-XOR על שני מספרים תתן תוצאה של מספר המורכב מביטים בהם מופיע "01" או "10" בשני המספרים.
לדוגמא:
ולכן XOR של המספר 3 ו- 5 ייתן את התוצאה 6.
אנחנו נשתמש בתכונות ה-XOR כדי לפתור את הבעיה:
- XOR בין אפס למספר ייתן תמיד את אותו המספר.
- XOR של אותם זוג מספרים זהה ייתן תמיד אפס.
כיון שאנו יודעים שבמערך קיימים זוגות של מספרים מלבד מספר יחיד, נוכל לעבור על המערך ולבצע XOR בין כל מספר למשתנה שיאותחל ל-אפס כך שבסוף המערך, אותו משתנה יקבל את הערך של המספר היחידי שלא היה לו זוג.
אין תגובות:
הוסף רשומת תגובה