Практика применения XOR в программировании

В данной статье я расскажу о битовой операции XOR (исключающее ИЛИ) и приведу наиболее интересные примеры ее применения на JAVA.

И так, XOR – операция, которая принимает значение «истина» только если всего один из аргументов имеет значение «истина».

XOR обладает следующими свойствами:

a XOR 0 = a
a XOR a = 0
a XOR b = b XOR a
(a XOR b) XOR b = a

В языке JAVA (а также в С, С++, C#, Ruby, PHP, JavaScript) операция обозначается символом «^».

Обмен значений переменных без использования дополнительной переменной

С использованием операции XOR можно реализовать обмен значений однотипных пременных без использования дополнительной переменной:

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

или в более короткой записи:

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

Таким образом можно, например, реализовать быстрый реверс текстовой строки:

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

Шифрование

Шифрование на основе операций XOR использует свойство:
(a XOR k) XOR k = a
где k – выступает в роли ключа

Простая реализация шифрования строки:

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

и дешифрования:

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

Попробуем зашифровать строку “Съешь ещё этих мягких французских булок, да выпей чаю.” И в качестве ключа возьмем слово “хабра”:

Узким местом такого шифрования является то, что зная часть зашифрованного текста можно с легкостью восстановить ключ и, соответственно, разшифровать весь текст. Поэтому в чистом виде он редко используется на практике, хотя его применяют как часть более сложных алгоритмов шифрования.
Интересно, что в свое время данный алгоритм использовался Microsoft для шифрования содержимого документов в Office 95.

Генератор случайных чисел XORShift

В 2003 году Джордж Марсаглия представил миру быстрый алгоритм генерации случайных чисел с использованием XOR – XORShift.

Одна из возможных его рализаций:

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

Тут “магические“ числа 21, 35 и 4 подобраны для генерации лучшей последовательности (полный период равен 2⁶⁴-1).
Проинициализировав генератор числом 1111111111 получим такую последовательность для первых 10 чисел:

39462749392662495
4596835458788324745
-7932128052244037525
-2502212788642280052
3288035714308340525
-8561046377475020727
-812160615072319265
-3869866974339671508
-7329504029400927428
3890915262874757420

В заключении просьба тем, у кого есть другие красивые примеры применения XOR, не вошедшие в статью, рассказать о них.