XOR operator
Lesson 6 of 17 in Coddy's Bit Manipulation course.
XOR ( ^ ) operator
Bitwise XOR takes two equal-length bit patterns. If not equal just push zeroes before the MSB of the shorter bit pattern. If both bits at compared position of the bit patterns are equal, the bit in resulting bit pattern is 0, otherwise 1.
'^' symbol is used to represent XOR operation.
When we talk mathematically we use '⊕' to represent XOR. So, in some questions you might come across this as well. Now let's make a table to see what XOR operator returns on all possible combinations of two bits.
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| x ^ y | 0 | 1 | 1 | 0 |
Let's take an example to understand the operation better-
In the example above we have done XOR operation on (11)10 and (2)10 which resulted in (9)10. We simply wrote these numbers in their binary form and compared the two bits, and followed the above definition of XOR operation.
Usage:
int a = 1;
int b = 0;
>> a ^ b
OUTPUT: 1Now, there are certain properties of XOR, that will cut short the time you will take to solve XOR related questions if you do not know these.
Some important properties of XOR
- x ⊕ 0 = x - If you XOR a number with zero, you will get the same number.
- x ⊕ x = 0 - If you XOR a number with itself, you will get zero.
- Let's take 2 numbers x and y. Let's say x ⊕ y = z. Then x ⊕ z = y and y ⊕ z = x are also valid equalities.
Challenge
MediumSean loves to wear socks and have different stylish socks in his closet. He keeps his socks with numbers written on them. For example- (1,1) , (10, 10) represent two sock pairs. Unfortunately one day a cat breaks in his closet and takes away a sock. The socks present in the closet are given to you as an array, complete the function MissingSock to find out which sock the cat took away.
For instance,
The original closet has 6 socks: 1, 1, 2, 3, 3, 2,
- 2 socks with the number
1 - 2 socks with the number
2 - 2 socks with the number
3
The cat came by and stole one sock numbered 1, The input now is: 1, 2, 3, 3, 2 because one sock numbered 1 is missing. The challenge is to find that missing sock (The output should be 1 because this is the missing sock)
Try it yourself
#include <iostream>
#include <vector>
using namespace std;
int MissingSock(vector<int> socks) {
// Write code here
}