What does the ^ (XOR) operator do?
MathOperatorsMath Problem Overview
What mathematical operation does XOR perform?
Math Solutions
Solution 1 - Math
XOR is a binary operation, it stands for "exclusive or", that is to say the resulting bit evaluates to one if only exactly one of the bits is set.
This is its function table:
a | b | a ^ b
--|---|------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
This operation is performed between every two corresponding bits of a number.
Example: 7 ^ 10
In binary: 0111 ^ 1010
0111
^ 1010
======
1101 = 13
Properties: The operation is commutative, associative and self-inverse.
It is also the same as addition modulo 2.
Solution 2 - Math
^
is the Python bitwise XOR operator. It is how you spell XOR
in python:
>>> 0 ^ 0
0
>>> 0 ^ 1
1
>>> 1 ^ 0
1
>>> 1 ^ 1
0
XOR stands for exclusive OR. It is used in cryptography because it let's you 'flip' the bits using a mask in a reversable operation:
>>> 10 ^ 5
15
>>> 15 ^ 5
10
where 5
is the mask; (input XOR mask) XOR mask gives you the input again.
Solution 3 - Math
A little more information on XOR operation.
- XOR a number with itself odd number of times the result is number itself.
- XOR a number even number of times with itself, the result is 0.
- Also XOR with 0 is always the number itself.
Solution 4 - Math
One thing that other answers don't mention here is XOR with negative numbers -
a | b | a ^ b
----|-----|------
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
While you could easily understand how XOR will work using the above functional table, it doesn't tell how it will work on negative numbers.
#How XOR works with Negative Numbers :
Since this question is also tagged as python, I will be answering it with that in mind. The XOR ( ^
) is an logical operator that will return 1 when the bits are different and 0 elsewhere.
A negative number is stored in binary as two's complement. In 2's complement, The leftmost bit position is reserved for the sign of the value (positive or negative) and doesn't contribute towards the value of number.
> In, Python, negative numbers are written with a leading one instead of a leading
> zero. So if you are using only 8 bits for your two's-complement
> numbers, then you treat patterns from 00000000
to 01111111
as the
> whole numbers from 0 to 127, and reserve 1xxxxxxx
for writing negative
> numbers.
With that in mind, lets understand how XOR works on negative number with an example. Lets consider the expression - ( -5 ^ -3 )
.
- The binary representation of
-5
can be considered as1000...101
and - Binary representation of
-3
can be considered as1000...011
.
Here, ...
denotes all 0s, the number of which depends on bits used for representation (32-bit, 64-bit, etc). The 1
at the MSB ( Most Significant Bit ) denotes that the number represented by the binary representation is negative. The XOR operation will be done on all bits as usual.
##XOR Operation :
-5 : 10000101 |
^ |
-3 : 10000011 |
=================== |
Result : 00000110 = 6 |
________________________________|
∴ -5 ^ -3 = 6
Since, the MSB becomes 0 after the XOR operation, so the resultant number we get is a positive number. Similarly, for all negative numbers, we consider their representation in binary format using 2's complement (one of most commonly used) and do simple XOR on their binary representation.
###The MSB bit of result will denote the sign and the rest of the bits will denote the value of the final result.
The following table could be useful in determining the sign of result.
a | b | a ^ b
------|-------|------
+ | + | +
+ | - | -
- | + | -
- | - | +
The basic rules of XOR remains same for negative XOR operations as well, but how the operation really works in negative numbers could be useful for someone someday .
Solution 5 - Math
Another application for XOR
is in circuits. It is used to sum bits.
When you look at a truth table:
x | y | x^y
---|---|-----
0 | 0 | 0 // 0 plus 0 = 0
0 | 1 | 1 // 0 plus 1 = 1
1 | 0 | 1 // 1 plus 0 = 1
1 | 1 | 0 // 1 plus 1 = 0 ; binary math with 1 bit
You can notice that the result of XOR
is x added with y, without keeping track of the carry bit, the carry bit is obtained from the AND
between x and y.
x^y // is actually ~xy + ~yx
// Which is the (negated x ANDed with y) OR ( negated y ANDed with x ).
Solution 6 - Math
The (^) XOR operator generates 1 when it is applied on two different bits (0 and 1). It generates 0 when it is applied on two same bits (0 and 0 or 1 and 1).