Biến XOR hoán đổi hoạt động như thế nào?

Question

Ai đó có thể giải thích cho tôi cách XOR hoán đổi hai biến không có biến tạm thời hoạt động?

void xorSwap (int *x, int *y) 
{ 
    if (x != y) { 
     *x ^= *y; 
     *y ^= *x; 
     *x ^= *y; 
    } 
} 

Tôi hiểu ĐIỀU GÌ, nhưng ai đó có thể hướng dẫn tôi về cách hoạt động của nó?

Answer 1

Bạn có thể xem làm thế nào nó hoạt động bằng cách làm thay:

x1 = x0 xor y0 
y2 = x1 xor y0 
x2 = x1 xor y2 

thay,

x1 = x0 xor y0 
y2 = (x0 xor y0) xor y0 
x2 = (x0 xor y0) xor ((x0 xor y0) xor y0) 

Bởi vì xor là hoàn toàn kết hợp và giao hoán:

y2 = x0 xor (y0 xor y0) 
x2 = (x0 xor x0) xor (y0 xor y0) xor y0 

Kể từ x xor x == 0 cho bất kỳ x,

y2 = x0 xor 0 
x2 = 0 xor 0 xor y0 

Và kể từ x xor 0 == x cho bất kỳ x,

y2 = x0 
x2 = y0 

Và hoán đổi được thực hiện.

Answer 2

Hầu hết mọi người sẽ trao đổi hai biến x và y sử dụng một biến tạm thời, như thế này:

tmp = x 
x = y 
y = tmp 

Dưới đây là một thủ thuật lập trình gọn gàng để trao đổi hai giá trị mà không cần một temp:

x = x xor y 
y = x xor y 
x = x xor y 

More chi tiết trong Swap two variables using XOR

Trên dòng 1 chúng tôi kết hợp x và y (sử dụng XOR) để có được điều này "hybri d ”và chúng tôi lưu trữ lại trong x. XOR là một cách tuyệt vời để lưu thông tin, bởi vì bạn có thể loại bỏ nó bằng cách thực hiện lại XOR.

Trên dòng 2. Chúng tôi XOR lai với y, trong đó hủy bỏ tất cả thông tin y, chỉ để lại cho chúng tôi với x. Chúng tôi lưu kết quả này trở lại vào y, vì vậy bây giờ họ đã đổi chỗ.

Trên dòng cuối cùng, x vẫn có giá trị lai. Chúng tôi XOR nó một lần nữa với y (bây giờ với giá trị ban đầu của x) để loại bỏ tất cả dấu vết của x ra khỏi lai. Điều này để lại cho chúng ta y và trao đổi hoàn tất!

---

Các máy tính thực sự có một tiềm ẩn “tạm thời” biến lưu trữ kết quả trung gian trước khi viết lại cho một thanh ghi. Ví dụ, nếu bạn thêm từ 3 đến một thanh ghi (trong giả ngôn ngữ máy):

ADD 3 A // add 3 to register A 

Các ALU (Arithmetic Logic Unit) thực sự là những gì thực hiện các hướng dẫn 3 + A. Nó lấy các đầu vào (3, A) và tạo ra một kết quả (3 + A), sau đó CPU sẽ lưu trữ trở lại vào thanh ghi gốc của A. Vì vậy, chúng tôi đã sử dụng ALU làm khoảng trống tạm thời trước khi chúng tôi có câu trả lời cuối cùng.

Chúng tôi lấy dữ liệu tạm thời tiềm ẩn của ALU, nhưng luôn ở đó. Theo cách tương tự, ALU có thể trả lại kết quả trung gian của XOR trong trường hợp x = x xor y, tại thời điểm đó CPU lưu trữ nó vào thanh ghi gốc của x.

Bởi vì chúng tôi không quen với suy nghĩ về ALU nghèo, bị bỏ quên, việc hoán đổi XOR có vẻ kỳ diệu vì nó không có biến tạm thời rõ ràng. Một số máy có lệnh trao đổi XCHG 1 bước để trao đổi hai thanh ghi.

Answer 3

Đây là một loại nên hơi dễ dàng hơn để grok:

int x = 10, y = 7; 

y = x + y; //x = 10, y = 17 
x = y - x; //x = 7, y = 17 
y = y - x; //x = 7, y = 10 

Bây giờ, người ta có thể hiểu được XOR lừa một chút dễ dàng hơn bằng cách hiểu rằng ^ có thể được coi như +hay-. Cũng như:

x + y - ((x + y) - x) == x 

, vì vậy:

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

Answer 4

Những người khác đã giải thích nó, bây giờ tôi muốn giải thích lý do tại sao nó là một ý tưởng tốt, nhưng bây giờ thì không.

Quay trở lại trong ngày khi chúng tôi có các chu kỳ đơn hoặc đa chu kỳ đơn giản, việc sử dụng thủ thuật này rẻ hơn để tránh các điều kiện bộ nhớ tốn kém hoặc làm cho sổ đăng ký tràn vào ngăn xếp. Tuy nhiên, bây giờ chúng ta có các CPU với các đường ống lớn. Đường ống của P4 dao động từ 20 đến 31 (hoặc hơn) các giai đoạn trong đường ống của họ, nơi bất kỳ sự phụ thuộc nào giữa việc đọc và ghi vào sổ đăng ký có thể khiến toàn bộ sự việc bị ngưng trệ. Việc hoán đổi xor có một số phụ thuộc rất lớn giữa A và B mà không thực sự quan trọng chút nào, nhưng ngăn chặn đường ống trong thực tế. Một đường ống bị trì hoãn gây ra một đường dẫn mã chậm, và nếu sự hoán đổi này nằm trong vòng lặp bên trong của bạn, bạn sẽ di chuyển rất chậm.

Trong thực tế chung, trình biên dịch của bạn có thể tìm ra những gì bạn thực sự muốn làm khi hoán đổi với biến tạm thời và có thể biên dịch nó thành một lệnh XCHG. Sử dụng hoán đổi xor làm cho nó khó khăn hơn nhiều cho trình biên dịch để đoán ý định của bạn và do đó ít có khả năng tối ưu hóa nó một cách chính xác. Chưa kể đến việc bảo trì mã, v.v.

Answer 5

@VonC có quyền, đó là một thủ thuật toán học gọn gàng. Hãy tưởng tượng 4 bit từ và xem nếu điều này giúp.

word1 ^= word2; 
word2 ^= word1; 
word1 ^= word2; 


word1 word2 
0101  1111 
after 1st xor 
1010  1111 
after 2nd xor 
1010  0101 
after 3rd xor 
1111  0101 

Answer 6

Về cơ bản có 3 bước trong phương pháp XOR:

một '= a XOR b (1)
b' = a' XOR b (2)
một”= a' XOR b'(3)

Để hiểu tại sao làm việc này lưu ý đầu tiên rằng:

1. XOR sẽ tạo ra 1 chỉ khi chính xác một trong số đó là toán hạng 1 và số còn lại bằng 0;
2. XOR là giao hoán để XOR b = b XOR a;
3. XOR là kết hợp như vậy (một XOR b) XOR c = một XOR (b XOR c); và
4. một XOR a = 0 (điều này nên được rõ ràng từ định nghĩa trong 1 trên)

Sau Bước (1), biểu diễn nhị phân của một sẽ có 1-bit chỉ ở các vị trí bit, nơi một và b có bit đối lập. Đó là một trong hai (ak = 1, bk = 0) hoặc (ak = 0, bk = 1). Bây giờ khi chúng ta làm sự thay thế ở bước (2), chúng tôi nhận được:

b'= (a b XOR) XOR b
= a XOR (b XOR b) vì XOR là kết
= a XOR 0 vì [4] trên
= a do định nghĩa của XOR (xem 1 trên)

Bây giờ chúng ta có thể thay thế vào Bước (3):

một”= (a XOR b) XOR một
= (b XOR a) XOR bởi vì XOR là comm utative
= b XOR (một XOR a) vì XOR là kết
= b XOR 0 vì [4] trên
= b do định nghĩa của XOR (xem 1 trên)

Thông tin chi tiết tại đây : Necessary and Sufficient

Answer 7

Lý do tại sao nó hoạt động là do XOR không mất thông tin. Bạn có thể làm điều tương tự với phép cộng và trừ thông thường nếu bạn có thể bỏ qua tràn. Ví dụ, nếu biến cặp A, B ban đầu chứa các giá trị 1,2, bạn có thể trao đổi chúng như thế này:

// A,B = 1,2 
A = A+B // 3,2 
B = A-B // 3,1 
A = A-B // 2,1 

BTW có một thủ thuật cũ để mã hóa một danh sách liên kết 2 chiều trong một "con trỏ đơn ". Giả sử bạn có một danh sách các khối bộ nhớ tại địa chỉ A, B, và C. Từ đầu tiên trong mỗi khối là, tương ứng:

// first word of each block is sum of addresses of prior and next block 
0 + &B // first word of block A 
&A + &C // first word of block B 
&B + 0 // first word of block C 

Nếu bạn có quyền truy cập để chặn A, nó cung cấp cho bạn địa chỉ của B Để đến được C, bạn lấy "con trỏ" trong B và trừ A, v.v. Nó hoạt động cũng như ngược lại. Để chạy dọc theo danh sách, bạn cần phải giữ con trỏ đến hai khối liên tiếp.Tất nhiên bạn sẽ sử dụng XOR thay vì cộng/trừ, vì vậy bạn sẽ không phải lo lắng về tràn.

Bạn có thể mở rộng điều này thành "web được liên kết" nếu bạn muốn có một số điều thú vị.

Answer 8

Là một lưu ý bên tôi được tái phát minh bánh xe này một cách độc lập cách đây vài năm theo hình thức số nguyên trao đổi bằng cách thực hiện:

a = a + b 
b = a - b (= a + b - b once expanded) 
a = a - b (= a + b - a once expanded). 

(này được đề cập ở trên trong một khó đọc chiều),

Các chính xác cùng một lý luận áp dụng cho xor hoán đổi: a^b^b = a và a^b^a = a. Kể từ khi xor là giao hoán, x^x = 0 và x^0 = x, điều này là khá dễ dàng nhận thấy kể từ

= a^b^b 
= a^0 
= a 

và

= a^b^a 
= a^a^b 
= 0^b 
= b 

Hope this helps. Lời giải thích này đã được đưa ra ... nhưng không rõ ràng lắm.

Answer 9

Tôi thích nghĩ về đồ họa hơn là số.

Hãy nói rằng bạn bắt đầu với x = 11 và y = 5 Trong nhị phân (và tôi sẽ sử dụng một máy 4 bit giả), đây là x và y

 x: |1|0|1|1| -> 8 + 2 + 1 
     y: |0|1|0|1| -> 4 + 1 

Bây giờ với tôi, XOR là một hoạt động đảo ngược và thực hiện nó hai lần là một tấm gương:

 x^y: |1|1|1|0| 
(x^y)^y: |1|0|1|1| <- ooh! Check it out - x came back 
(x^y)^x: |0|1|0|1| <- ooh! y came back too!