The practice of using XOR in programming

In this article I will talk about the XOR bit operation (exclusive OR) and give the most interesting examples of its application on 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) operation is indicated by the symbol “^”.

Exchange variable values ​​without using an additional variable

Using the XOR operation, it is possible to exchange the values ​​of the same type of 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, it is possible, for example, to implement reverse text string:

	  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);
	    }		  

However, it should be noted that such a code does not give a gain in speed compared to 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

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 decryption:

	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 more of these soft French rolls, but have some tea.” And take the word “habr” as the key: The



bottleneck of such encryption is that knowing a part of the encrypted text, you can easily recover 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.
It is interesting that 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 random number generation algorithm using XOR - XORShift .

One of its possible implementations:

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).
Initializing the generator number 1111111111, we obtain a sequence for the first 10 numbers:

39462749392662495
4596835458788324745
-7,932,128,052,244,037,525
-2,502,212,788,642,280,052
3288035714308340525
-8,561,046,377,475,020,727
-812160615072319265
-3,869,866,974,339,671,508
-7,329,504,029,400,927,428
3890915262874757420

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