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

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

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

image



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 подобраны для генерации лучшей последовательности (полный период равен 264-1).
Проинициализировав генератор числом 1111111111, получим такую последовательность для первых 10 чисел:

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

В заключение просьба тем, у кого есть другие красивые примеры применения XOR, не вошедшие в статью, рассказать о них.
Поделиться публикацией
Комментарии 53
    –2
    (del)
      +2
      Заменить одно значение на другое в переменной, которая может принимать только эти два значения:
      v ^= val1 ^ val2;
        0
        Как просто. А я городил штуки вроде v = (val1 + val2) - v;
        +8
        Обмен значений местами без дополнительной переменной — разве что демонстрация любопытных свойств операции xor. В реальном коде такой подход имеет только недостатки — код нечитаем, работает многократно медленнее, область применения ограничена только базовыми числовыми типами.
          +6
          И стоит добавить, что неявно переменная (а точнее память) таки используется — регистры или стек.
            0
            public XORShift(long rnd) { this.rnd = rnd; }

            Инициализирующее значение для конгруэнтных гпсч обычно называют seed.
            P.S. промахнулся
              0
              Действительно XOR работает медленнее, но не многократно а приблизительно в 3-4 раза медленнее
              в сравнении с кодом использующим временную переменную (проверял на HotSpot 7).

              	  public static final String reverseWithVar(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++) {
              	        	char temp = array[i];
              	        	array[i] = array[length - i - 1];
              	        	array[length - i - 1] = temp;
              	        }
              	        return String.valueOf(array);
              	    }	
              
                0
                Внес в статью правку о том, что обмен значениями через XOR не дает выигрыша в скорости.
                Спасибо.
                  0
                  По идее у х86 есть инструкция как раз для обмена значений местами без использования доп регистров или памяти — XCHG, интересно её современные компиляторы используют?
                    +2
                    XCHG interlocked, поэтому он намного медленнее, и блокирует потоки на других ядрах.
                      +1
                      … если обращается к памяти. Если использовать с регистрами, получится тот же самый дополнительный регистр, только обратно в память в другом порядке данные заноситься будут, как если бы XCHG не было.
                        0
                        … в порядке, обратном тому, как если бы XCHG не было. *
                      +1
                      1. всё равно одно из значений надо будет выгружать на регистр, а потом обратно в память, потому что xchg не умеет память-память.
                      2. используют, для спин-блокировок, например.
                    +14
                    Теперь, пожалуйста, статью про «and» или про «not.»
                      +2
                      Конечно, сначала базис. А потом можно переходить и к сложным вещам. Штрих Шеффера изучить, например :)
                      +11
                      RAID 5.
                      Система состоит из (минимум) трёх жёстких дисков: два из них содержат по половине информации, а третий — результат побитового XOR между ними. Если любой из жёстких дисков выходит из строя, его содержимое можно восстановить, применив XOR к двум оставшимся.
                        +1
                        Не знаю, как на Java, но на C/C++ нормальные компиляторы используют для обмена регистр вместо дополнительной переменной.
                          0
                          Вы так говорите, будто регистр — не переменная.
                            –2
                            Переменная на стеке находится, а стек — это RAM, ну если повезёт, то кеш, доступ медленнее, чем к регистрам.
                              +5
                              Переменная — это абстракция. Компилятор где захочет, там и будет её хранить. Захочет — на стеке (как все привыкли), захочет в куче (впрочем зачем бы ему это делать, да и не уверен что это не нарушит каких-нибудь гарантий), захочет — в регистре (очень часто бывает). Ну и раньше даже ключевое слово было «register» — когда программист намекает компилятору что эту переменную лучше хранить в регистре, «auto» — что это переменную можно хранить где угодно (по умолчанию). Захочет — вообще удалит переменную при оптимизации. Захочет — часть времени будет хранить переменную на стеке — часть — на регистре. Захочет — переупорядочит инструкции, у него очень много свободы.

                              Это я к тому, что до компиляции есть переменные. После компиляции есть регистры, стек и куча. Одновременно эти понятия не существуют, так что противопоставлять переменные регистрам некорректно.

                              P.S. — с тем что написано по ссылке, полностью согласен. Причём можно условно сказать что компилятор не выкинул переменную t, а хранил её в регистре «eax»

                              А мог (в ассемблере не силён, так что псевдокод), действительно выкинуть её:
                              xchg [a], [b]
                              
                                0
                                Не мог.
                                Во-первых, xchg mem, mem не существует.
                                Во-вторых, xchg блокирует потоки.
                                Я говорю про то, что на стеке, который медленнее регистров, временной переменной не создаётся, используется регистр, а значит, лучше использовать временную переменную, а не XOR.
                                  0
                                  Ну то что лучше использовать временную переменную — с этим никто не спорит, претензия была лишь к терминологии.
                            0
                            Байткод Java (HotSpot 7):

                            Временная переменная
                            int a = 7;
                            int b = 9;
                            
                            int t = a;
                            a = b;
                            b = t;
                            


                            0: bipush        7
                            1: istore_1
                            2: bipush        9
                            4: istore_2
                            
                            5: iload_1
                            6: istore_3
                            7: iload_2
                            8: istore_1
                            9: iload_3
                            10: istore_2
                            

                            XOR
                            int a = 7;
                            int b = 9;
                            
                            a = a^b;
                            b = a^b;
                            a = a^b;
                            


                            0: bipush        7
                            1: istore_1
                            2: bipush        9
                            4: istore_2
                            
                            5: iload_1
                            6: iload_2
                            7: ixor
                            8: istore_1
                            9: iload_1
                            10: iload_2
                            11: ixor
                            12: istore_2
                            13: iload_1
                            14: iload_2
                            15: ixor
                            16: istore_1
                            


                            В Java таки используется дополнительная переменная (было бы странно ожидать что-то другое). На самом деле это даже хорошо, т.к. негоже высокоуровнему языку иметь прямой доступ к регистрам.
                              0
                              То есть в байткоде Java нет регистров (пусть и виртуальных, но в рантайме маппящихся на реальные)?

                              Взглянув на описание языка в вики пришёл к выводу что вместо регистров тут используется вспомогательный стек.
                              Но тогда почему бы не сделать так? Вспомогательного стека на две переменные не хватит?
                              iload_1
                              iload_2
                              istore_1
                              istore_2
                              


                              Или же приведённый Вами байткод получается из кода на Java «дословно», без оптимизаций, а оптимизироваться будет в рантайме (JIT?)
                                0
                                В Dalvik (JVM на Android) есть, можно посмотреть, как там (но там регистры не машинные, а наподобие локальных переменных в C/C++, возможно, реализация использует стек, то есть вычитание из esp).
                                  +1
                                  Так, как вы написали, не делается, поскольку байт-код не выполняется напрямую, и оценить скорость его выполнения не переводя его в машинный код — довольно сложно. Я не удивлюсь, если JIT на оба варианта (обмен через переменную и через стек) генерирует одинаковый машинный код.
                              +2
                              Алгоритмы блочного шифрования: AES, DES, Feistel cipher, а также во множестве других мест в криптографии 1 и 2.
                                0
                                Кстати, а почему у вас в коде названия массивов с p начинаются? В венгерской нотации p — это pointer, а в Java их нет.
                                  0
                                  Если имеется ввиду тут
                                  byte[] pText, String pKey
                                  

                                  то p — это parameter.
                                    0
                                    А, да, не заметил byte[] txt = pText.getBytes();.
                                  +4
                                  Можно найти минимум без ветвлений кода:
                                  min = y ^ ((x ^ y) & -(x < y))
                                  И много других фишек, которые есть тут.
                                    +1
                                    В языках, где допустимо выражение -(x < y). В C# и Java все равно получится условие.
                                      0
                                      А разве не boolean получится?
                                      Тогда не -(x < y), а -((int)(x < y)).
                                        0
                                        Так тоже нельзя. Нельзя привести булеан к инту здесь.
                                      +2
                                      «Hacker's Delight» ещё. Хорошая книжка.
                                      +5
                                      xor eax, eax — можно так обнулять регистр, по идее быстрее, чем mov eax, 0.
                                        +3
                                        Компиляторы так и делают если вы напишете
                                        int x = 0;
                                        
                                          0
                                          Пост о том, что переменная может находиться не только в регистре.
                                            0
                                            Не пост, а комментарий.
                                          +1
                                          Не только быстрей, но и меньше байт занимает машинная команда (во время исполнения).
                                            +1
                                            Собственно, потому и быстрей.
                                              0
                                              Не совсем поэтому. Связи между длиной команды и количеством тактов нету. Хотя теоретически (очень сильно теоретически) короткие команды в кеше предпочтительнее по скорости. Но в современных процессорах скорость выполнения даже тактами просто так не подсчитать, а длиной команд и подавно. Да и здесь кол-во тактов одинаково, но xor на одном регистре лучше по некоторым причинам, например, отсутствие зависимости (в данном случае ложной, как я понимаю) на eax, что позволяет параллелить с командой до/после. Плюс для некоторых команд на одном регистре, xor в том числе, есть какая-то оптимизация в более-менее новых пентиумах, подробности забыл, извините, давно не занимался)
                                                0
                                                Как раз именно при операции xor ложная зависимость и возникает: если mov затирает старое значение в eax, то xor его вроде как использует (если только операция «обнуления» не была оптимизирована отдельно).
                                                  +4
                                                  Операции обнуления в современных процессорах как раз оптимизируются отдельно:
                                                  Use one of these dependency breaking idioms to clear a register when possible.
                                                  • XOR REG,REG
                                                  • SUB REG,REG
                                                  • PXOR/VPXOR XMMREG,XMMREG
                                                  • PSUBB/W/D/Q XMMREG,XMMREG
                                                  • VPSUBB/W/D/Q XMMREG,XMMREG
                                                  • XORPS/PD XMMREG,XMMREG
                                                  • VXORPS/PD YMMREG, YMMREG
                                                  Since zero idioms are detected and removed by the renamer, they have no execution latency.
                                                  Более подробно – в Intel® 64 and IA-32 Architectures Optimization Reference Manual, страница 43.
                                                  0
                                                  А использование imm операнда (который указан непосредственно в инструкции, в данном случае — 0) может влиять на скорость? Понятно, что если брать из памяти — mov eax, [00040100h], где по 0x00040100 лежит 0 — однозначно медленнее.
                                                    0
                                                    Может, так как этот 0 ещё и прочесть надо, прежде чем попытаться оптимизировать, а регистры (в случае xor/sub) задаются прямо в том же слове, что и опкод.
                                                      0
                                                      Если 0 идет как imm — то он читается вместе с инструкцией. Хотя кто его знает, тут уже сложный процесс. И вот в чем беда низкоуровневого кодинга — с точки зрения быстродействия мы вряд-ли что-то выиграем, оптимизирую то, о чем мы говорим.
                                                        0
                                                        Да, читается вместе с инструкцией, но читать приходится больше байт (6), чем если бы использовался XOR (всего 2 байта), в этом и заключается медлительность.
                                                        И этот 0 жрёт кеш-память.
                                                          0
                                                          Не 6, а 5, точнее.
                                                          А вообще, не совместно с инструкцией. Сначала инструкция декодируется, потом так как r/m является imm, читается этот самый 0.
                                            +4
                                            XOR-связный список
                                            Cтруктура данных, похожая на обычный двусвязный список, однако в каждом элементе хранящая только один адрес — результат выполнения операции XOR над адресами предыдущего и следующего элементов списка. Для того, чтобы перемещаться по списку, необходимо взять два последовательных адреса и выполнить над ними операцию XOR, которая и даст реальный адрес следующего элемента.
                                              0
                                              Метрику Хэмминга в тред!
                                                0
                                                Интересно, насколько сильно коррелированы будут такие случайные числа. Подозреваю, что достаточно сильно, чтобы можно было использовать их на практике, например, в статмоделировании.
                                                  0
                                                  А у меня в коридоре 2 выключателя света, работающие по XORу.

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое