Практика применения 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, не вошедшие в статью, рассказать о них.

Автор: fealsoft

Источник