Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What are some practical applications of XOR in algorithms [closed]

To be honest I am rusty in bit operations.
What I am interested in is the XOR operation. Well, I know what it does bitwise, and that it is used in encryption and that we can do swapping without any temporary variable, but I was interested if there are specific approaches in algorithms that XOR's properties fit.
I mean I am interested in practical applications of XOR in algorithms (e.g. we could use it to finding unique element among duplicates). Is there a pattern of problems (or a formulation of a problem) that one could see that the use of XOR is the way to go? (Same way as there is a pattern when to use binary search?)
Is there some list of practical applications of XOR on algorithms that is related to the core algorithm, not simply use it e.g. to do math operations faster like we can use >> instead of divide by 2.

Any input is welcome

like image 947
Cratylus Avatar asked Apr 23 '12 19:04

Cratylus


People also ask

What can XOR be used for?

The XOR Function[1] was introduced in Excel 2013 and is available under Excel Logical functions. It is a logical “exclusive OR” function. For two given logical statements, the XOR function would return TRUE if one of the statements is true and FALSE if both statements are true.

Where is XOR used in programming?

The ^ (bitwise XOR) in C or C++ takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different. The << (left shift) in C or C++ takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift.

What is the significance of XOR?

(eXclusive OR) A Boolean logic operation that is widely used in cryptography as well as in generating parity bits for error checking and fault tolerance. XOR compares two input bits and generates one output bit. The logic is simple. If the bits are the same, the result is 0.

What is XOR in algorithm?

In computer programming, the exclusive or swap (sometimes shortened to XOR swap) is an algorithm that uses the exclusive or bitwise operation to swap the values of two variables without using the temporary variable which is normally required.


1 Answers

A few examples that came up in my mind:

Toggling bits:

int i = 123;
i ^= (1 << 4); // toggle bit 5

Some kind of randomness:

int i = 123;
for (int k = 0; k < 100; k++)
{
   i = i ^ (i << 1) + i;
   System.out.println(i);
}

"Weak Encryption":

int b = 235321;
int key = 24552;
int encrypted = b ^ key;
int decrypted = encrypted ^ key; // equals 235321
like image 131
Martijn Courteaux Avatar answered Sep 28 '22 08:09

Martijn Courteaux