Practice of using XOR in programming

In this article I will talk about the bit operation XOR (exclusive OR) and give the most interesting examples of its use in JAVA.



So, XOR is an operation that takes the value "true" only if only one of the arguments has the value "true."





')





XOR has the following properties:



a XOR 0 = a

a XOR a = 0

a XOR b = b XOR a

(a XOR b) XOR b = a



In the JAVA language (as well as in C, C ++, C #, Ruby, PHP, JavaScript) the operation is denoted by the symbol “^”.

Exchange of variable values ​​without using an additional variable

Using the XOR operation, you can implement the exchange of values ​​of the same type variables without using an additional variable:

int x = 5, y = 7; x = x^y; // x == 2 y = x^y; // y == 5 x = x^y; // x == 7 

or in a shorter record:

  y ^= (x ^= y); x ^= y; 

Thus, you can, for example, implement the reverse of a text line:

  public static final String reverseWithXOR(String string) { char[] array = string.toCharArray(); int length = array.length; int half = (int) Math.floor(array.length / 2); for (int i = 0; i < half; i++) { array[i] ^= array[length - i - 1]; array[length - i - 1] ^= array[i]; array[i] ^= array[length - i - 1]; } return String.valueOf(array); } 

It should be noted, however, that such a code does not provide a gain in speed as compared with a code using a temporary variable.

Encryption

Encryption based on XOR operations uses the property:

(a XOR k) XOR k = a

where k - acts as a key



A simple implementation of string encryption:

  public static byte[] encode(String pText, String pKey) { byte[] txt = pText.getBytes(); byte[] key = pKey.getBytes(); byte[] res = new byte[pText.length()]; for (int i = 0; i < txt.length; i++) { res[i] = (byte) (txt[i] ^ key[i % key.length]); } return res; } 

and decrypt:

  public static String decode(byte[] pText, String pKey) { byte[] res = new byte[pText.length]; byte[] key = pKey.getBytes(); for (int i = 0; i < pText.length; i++) { res[i] = (byte) (pText[i] ^ key[i % key.length]); } return new String(res); } 

Let's try to encrypt the line “Eat these soft French buns, and drink tea.” And as a key, take the word “habr”:







The bottleneck of such encryption is that knowing a part of the ciphertext you can easily restore the key and, accordingly, decrypt the entire text. Therefore, in its pure form, it is rarely used in practice, although it is used as part of more complex encryption algorithms.

Interestingly, at one time this algorithm was used by Microsoft to encrypt the contents of documents in Office 95.

XORShift random number generator

In 2003, George Marsaglia introduced the world to a fast algorithm for generating random numbers using XOR - XORShift .



One of its possible razlizatsy:

 class XORShift { private long rnd; public XORShift(long rnd) { this.rnd = rnd; } public long getRandom() { this.rnd ^= (this.rnd << 21); this.rnd ^= (this.rnd >>> 35); this.rnd ^= (this.rnd << 4); return this.rnd; } } 

Here the “magic” numbers 21, 35 and 4 are selected to generate the best sequence (the full period is 2 ⁶⁴ -1).

After initializing the generator with the number 1111111111, we get the following sequence for the first 10 numbers:



39462749392662495

4596835458788324745

-7932128052244037525

-2502212788642280052

3288035714308340525

-8561046377475020727

-812160615072319265

-3869866974339671508

-7329504029400927428

3890915262874757420



In conclusion, please those who have other beautiful examples of XOR, not included in the article, tell us about them.