Почему "a ^ = b ^ = a ^ = b;" отличной от "a ^ = b; b ^ = a; a ^ = b;"?

Я попробовал код для обмена двумя целыми числами в Java без использования третьей переменной, используя XOR.

Вот две функции подкачки, которые я пробовал:

package lang.numeric;

public class SwapVarsDemo {

    public static void main(String[] args) {
        int a = 2984;
        int b = 87593;
        swapDemo1(a,b);
        swapDemo2(a,b);
    }

    private static void swapDemo1(int a, int b) {
        a^=b^=a^=b;
        System.out.println("After swap: "+a+","+b);
    }

    private static void swapDemo2(int a, int b) {
        a^=b;
        b^=a;
        a^=b;
        System.out.println("After swap: "+a+","+b);
    }

}

Результат, полученный этим кодом, был следующим:

After swap: 0,2984
After swap: 87593,2984

Мне любопытно узнать, почему это утверждение:

        a^=b^=a^=b;

отличается от этого?

        a^=b;
        b^=a;
        a^=b;

Ответы

Ответ 1

Проблема заключается в порядке оценки:

См. раздел JLS 15.26.2

Сначала левый операнд оценивается для создания переменной. Если эта оценка завершается внезапно, тогда выражение присваивания внезапно завершается по той же причине; правый операнд не оценивается и не выполняется присвоение.

В противном случае значение левого операнда сохраняется, а затем правый операнд. Если эта оценка завершается резко, тогда выражение присваивания резко завершается для та же причина и отсутствие назначения.

В противном случае сохраненное значение левой переменной и значение правый операнд используется для выполнения двоичной операции обозначенный оператором составного присваивания. Если эта операция завершается внезапно, тогда выражение присваивания резко завершается по той же причине и без присвоения.

В противном случае результат двоичной операции преобразуется в тип левой переменной, подвергнутой преобразованию набора значений (п. 5.1.13) к соответствующему стандартному значению (не значение с расширенным показателем set), и результат преобразования сохраняется в переменной.

Итак, ваше выражение:

a^=b^=a^=b;

оцените a
оцените b^=a^=b
xor два (так что a на первом этапе не имеет к нему ^=b)
сохраните результат в a

Другими словами, ваше выражение эквивалентно следующему java-коду:

    int a1 = a;
    int b2 = b;
    int a3 = a;
    a = a3 ^ b;
    b = b2 ^ a;
    a = a1 ^ b;

Вы можете видеть это из дизассемблированной версии вашего метода:

  private static void swapDemo1(int, int);
    Code:
       0: iload_0       
       1: iload_1       
       2: iload_0       
       3: iload_1       
       4: ixor          
       5: dup           
       6: istore_0      
       7: ixor          
       8: dup           
       9: istore_1      
      10: ixor          
      11: istore_0

Ответ 2

Поскольку a ^= b ^= a ^= b; анализируется как:

a ^= (b ^= (a ^= b));

Что можно свести к:

a ^= (b ^= (a ^ b));

Итак, b будет иметь значение b ^ (a ^ b) и, наконец, a будет a ^ (b ^ (a ^ b).

Ответ 3

Это очень похоже на запись в книге Блоха и блоха Блоха (см. главу 2, головоломка 7 ( "Swap Meat" ). Я не могу улучшить его.

Объяснение в решении:

Эта идиома использовалась на языке программирования C и оттуда его путь в С++, но не гарантированно работает в любом из этих языки. Гарантируется, что он не будет работать на Java. Язык Java спецификация говорит, что операнды операторов вычисляются слева направо [JLS 15.7]. Чтобы оценить выражение x ^= expr, значение x выбирается перед вычислением expr, а Исключительное ИЛИ этих двух значений присваивается переменной x [JLS 15.26.2]. В программе CleverSwap переменная x отбирается дважды - один раз для каждого появления в выражении - но обе выборки происходят перед любыми присвоениями. Следующий фрагмент кода описывает поведение сломанной подкачки идиомы более подробно и объясняет которые мы наблюдали:

Код, указанный в приведенной выше цитате:

// The actual behavior of x ^= y ^= x ^= y in Java
int tmp1 = x;     // First appearance of x in the expression
int tmp2 = y;     // First appearance of y
int tmp3 = x ^ y; // Compute x ^ y
x = tmp3;         // Last assignment: Store x ^ y in x
y = tmp2 ^ tmp3;  // 2nd assignment: Store original x value in y
x = tmp1 ^ y;     // First assignment: Store 0 in x

Ответ 4

Проверьте приоритет оператора (ref: http://introcs.cs.princeton.edu/java/11precedence/ в результате поиска приоритета java-оператора). Здесь приведена ссылка на документацию Oracle (http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html), хотя она немного плотная).

В частности, ^ = обрабатывается справа налево (не слева направо)

Ответ 5

Второй вариант равен

a=a^(b^(a^b));

Ответ 6

У меня недостаточно очков репутации, чтобы прокомментировать ответ Натана.

@Ответ Натана Хьюза, говорящий о книге Java Puzzlers, находится на месте, и его ответ указывает на некоторые идеи, которые позволяют вам сделать это в 1 строке. Хотя и не так элегантно, как вопрос OP.

Как указывает Натан:

В программе CleverSwap переменная x отбирается дважды - один раз для каждого выражения в выражении - но оба семплирования встречаются перед любыми присваиваниями

Также, используя https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html, вы можете сделать это в 1 строке:

a = ( b = (a = a ^ b) ^ b) ^ a;

Ключ является присвоением значения переменной как части первого XOR, гарантирующего, что вы сохраните это в левой части второго XOR (см. ссылку jls выше, для хорошего примера назначения в левом операнде). Аналогично, установив переменную b с результатами второго XOR, снова оставив слева от окончательного XOR.