Câu hỏi Tại sao trao đổi giá trị với XOR thất bại khi sử dụng hình thức hợp chất này?


Tôi tìm thấy mã này để trao đổi hai số mà không sử dụng biến thứ ba, sử dụng XOR ^ nhà điều hành.

Mã số: 

int i = 25;
int j = 36;
j ^= i;       
i ^= j;
j ^= i;

Console.WriteLine("i:" + i + " j:" + j);

//numbers Swapped correctly
//Output: i:36 j:25

Bây giờ tôi đã thay đổi mã trên thành mã tương đương này.

Ma cua toi: 

int i = 25;
int j = 36;

j ^= i ^= j ^= i;   // I have changed to this equivalent (???).

Console.WriteLine("i:" + i + " j:" + j);

//Not Swapped correctly            
//Output: i:36 j:0

Bây giờ, tôi muốn biết, Tại sao mã của tôi cho đầu ra không chính xác?


76
2018-04-07 06:56


gốc


Nó sẽ là câu trả lời giống như được đưa ra cho: stackoverflow.com/questions/3741440 hoặc nhiều người khác trong cột Liên quan. Mặc dù họ nói C ++ và đây là C #, các quy tắc tương tự sẽ được áp dụng. - Daemin
@Daemin: Không, các quy tắc tương tự không ứng dụng. Đó là hành vi không xác định trong C + +, nhưng tôi không tin rằng nó không xác định trong C #. - Jon Skeet
@Daemin - Đây là bài viết liên quan của Eric Lippert, chỉ hai ngày trước: stackoverflow.com/questions/5538193/… cụ thể là: "Các câu trả lời khác chỉ ra rằng trong ngôn ngữ lập trình C và C ++, các đặc tả ngôn ngữ không xác định thứ tự tác dụng phụ nào xảy ra nếu tác dụng phụ và quan sát của nó nằm trong cùng một" điểm chuỗi ", họ đang ở đây. [...] C # không cho phép loại điều đó. Trong C #, một tác dụng phụ ở bên trái được quan sát là đã xảy ra vào lúc mà đoạn mã bên phải thực thi. " - Kobi
Một ngày nào đó tôi muốn nghĩ về một câu hỏi đủ thú vị để Jon Skeet tweet về ... - David Johnstone
Đối với những người đã đóng câu hỏi - câu hỏi khác đề cập đến C, C ++ trong đó kết quả là không xác định do thiếu các điểm chuỗi. Trong khi câu hỏi này đề cập đến C #, câu trả lời được xác định rõ, nhưng khác với những gì có thể được mong đợi. Vì vậy, tôi sẽ không coi nó như là một câu hỏi trùng lặp, bởi vì các câu trả lời là khác biệt rõ rệt. - Damien_The_Unbeliever


Các câu trả lời:


EDIT: Được rồi, đã nhận nó.

Điểm đầu tiên cần làm là rõ ràng bạn không nên sử dụng mã này. Tuy nhiên, khi bạn mở rộng nó, nó sẽ trở thành tương đương với:

j = j ^ (i = i ^ (j = j ^ i));

(Nếu chúng ta sử dụng một biểu thức phức tạp hơn như foo.bar++ ^= i, điều quan trọng là ++ chỉ được đánh giá một lần, nhưng ở đây tôi tin rằng nó đơn giản hơn.)

Bây giờ, thứ tự đánh giá của các toán hạng luôn luôn là trái sang phải, do đó, để bắt đầu với chúng ta nhận được:

j = 36 ^ (i = i ^ (j = j ^ i));

Điều này (ở trên) là bước quan trọng nhất. Chúng tôi đã kết thúc với 36 là LHS cho các hoạt động XOR được thực hiện cuối cùng. LHS không phải là "giá trị của j sau khi đánh giá RHS ".

Việc đánh giá RHS của ^ liên quan đến biểu thức "một cấp lồng nhau", vì vậy nó sẽ trở thành:

j = 36 ^ (i = 25 ^ (j = j ^ i));

Sau đó, nhìn vào mức độ sâu nhất của làm tổ, chúng ta có thể thay thế cả hai i và j:

j = 36 ^ (i = 25 ^ (j = 25 ^ 36));

... trở thành

j = 36 ^ (i = 25 ^ (j = 61));

Bài tập cho j trong RHS xảy ra đầu tiên, nhưng kết quả sau đó được ghi đè vào cuối anyway, vì vậy chúng tôi có thể bỏ qua điều đó - không có đánh giá thêm về j trước bài tập cuối cùng:

j = 36 ^ (i = 25 ^ 61);

Điều này bây giờ tương đương với:

i = 25 ^ 61;
j = 36 ^ (i = 25 ^ 61);

Hoặc là:

i = 36;
j = 36 ^ 36;

Trở thành:

i = 36;
j = 0;

tôi suy nghĩ đó là tất cả chính xác, và nó được câu trả lời đúng ... xin lỗi Eric Lippert nếu một số chi tiết về thứ tự đánh giá là hơi off: (


76
2018-04-07 07:07



IL cho rằng đây chính là điều xảy ra. - SWeko
@ Lasse: Tuyệt đối. Mã như thế này thật khủng khiếp. - Jon Skeet
Tại sao lại là một trong những chuyên gia C # vĩ đại nhất với các trạng thái tần số như vậy "bạn không nên sử dụng mã này" trong SO câu trả lời? ;-) - Fredrik Mörk
@ Fredrik: Trong trường hợp này tôi đã không đưa ra mã để bắt đầu. Nó hơi khác khi ai đó hỏi làm sao bạn có thể đạt được điều gì đó và tôi có nguồn gốc mã khủng khiếp :) - Jon Skeet
Điều đó có vẻ đúng với tôi. - Eric Lippert


Kiểm tra IL tạo ra và nó cho ra kết quả khác nhau;

Việc hoán đổi chính xác tạo ra một cách đơn giản:

IL_0001:  ldc.i4.s   25
IL_0003:  stloc.0        //create a integer variable 25 at position 0
IL_0004:  ldc.i4.s   36
IL_0006:  stloc.1        //create a integer variable 36 at position 1
IL_0007:  ldloc.1        //push variable at position 1 [36]
IL_0008:  ldloc.0        //push variable at position 0 [25]
IL_0009:  xor           
IL_000a:  stloc.1        //store result in location 1 [61]
IL_000b:  ldloc.0        //push 25
IL_000c:  ldloc.1        //push 61
IL_000d:  xor 
IL_000e:  stloc.0        //store result in location 0 [36]
IL_000f:  ldloc.1        //push 61
IL_0010:  ldloc.0        //push 36
IL_0011:  xor
IL_0012:  stloc.1        //store result in location 1 [25]

Việc hoán đổi không chính xác tạo ra mã này:

IL_0001:  ldc.i4.s   25
IL_0003:  stloc.0        //create a integer variable 25 at position 0
IL_0004:  ldc.i4.s   36
IL_0006:  stloc.1        //create a integer variable 36 at position 1
IL_0007:  ldloc.1        //push 36 on stack (stack is 36)
IL_0008:  ldloc.0        //push 25 on stack (stack is 36-25)
IL_0009:  ldloc.1        //push 36 on stack (stack is 36-25-36)
IL_000a:  ldloc.0        //push 25 on stack (stack is 36-25-36-25)
IL_000b:  xor            //stack is 36-25-61
IL_000c:  dup            //stack is 36-25-61-61
IL_000d:  stloc.1        //store 61 into position 1, stack is 36-25-61
IL_000e:  xor            //stack is 36-36
IL_000f:  dup            //stack is 36-36-36
IL_0010:  stloc.0        //store 36 into positon 0, stack is 36-36 
IL_0011:  xor            //stack is 0, as the original 36 (instead of the new 61) is xor-ed)
IL_0012:  stloc.1        //store 0 into position 1

Hiển nhiên rằng mã được tạo trong phương thức thứ hai được kết hợp, vì giá trị cũ của j được sử dụng trong một phép tính, nơi giá trị mới được yêu cầu.


15
2018-04-07 07:18



Tôi đã kiểm tra đầu ra và nó cho kết quả khác nhau :). Câu hỏi đặt ra là tại sao điều đó lại xảy ra ... - Kobi
Vì vậy, nó tải tất cả các giá trị cần để đánh giá toàn bộ biểu thức trên ngăn xếp trước, sau đó xoring và lưu các giá trị vào các biến khi nó đi (vì vậy nó sẽ sử dụng các giá trị ban đầu của i và j trong suốt quá trình đánh giá biểu thức) - Damien_The_Unbeliever
Đã thêm giải thích cho IL thứ hai - SWeko
Thật đáng tiếc là mã trao đổi không chỉ là ldloc.0; ldloc.1; stloc.0; stloc.1. Trong C # anyway; nó hoàn toàn hợp lệ IL. Bây giờ tôi nghĩ về nó ... tôi tự hỏi liệu C # sẽ tối ưu hóa biến temp ra khỏi một trao đổi. - cHao


C # tải j, i, j, i trên ngăn xếp và lưu trữ từng XOR kết quả mà không cập nhật ngăn xếp, vì vậy ngoài cùng bên trái XOR sử dụng giá trị ban đầu cho j.


7
2018-04-07 07:22





Viết lại:

j ^= i;       
i ^= j;
j ^= i;

Mở rộng ^=:

j = j ^ i;       
i = j ^ i;
j = j ^ i;

Thay thế:

j = j ^ i;       
j = j ^ (i = j ^ i);

Thay thế điều này chỉ hoạt động nếu / vì phía bên tay trái của toán tử ^ được đánh giá đầu tiên:

j = (j = j ^ i) ^ (i = i ^ j);

Sự sụp đổ ^:

j = (j ^= i) ^ (i ^= j);

Đối xứng:

i = (i ^= j) ^ (j ^= i);

0
2017-11-21 18:29