ในการเขียนโปรแกรมคอมพิวเตอร์การดำเนินการสลับค่าแบบเอกซ์คลูซีฟหรือ (บางครั้งย่อว่าXOR swap ) เป็นอัลกอริธึมที่ใช้การดำเนินการบิตแบบเอกซ์คลูซีฟหรือ เพื่อสลับค่าของตัวแปร สองตัว โดยไม่ต้องใช้ตัวแปรชั่วคราวซึ่งโดยปกติแล้วจำเป็นต้องใช้

อัลกอริทึมนี้เป็นเพียงนวัตกรรมและเป็นวิธีสาธิตคุณสมบัติของ การดำเนินการ แบบ Exclusive OR เท่านั้นบางครั้งมีการกล่าวถึงว่าเป็นวิธีการเพิ่มประสิทธิภาพของโปรแกรมแต่แทบไม่มีกรณีใดเลยที่การสลับโดยใช้Exclusive ORจะให้ประโยชน์มากกว่าเทคนิคมาตรฐานที่เห็นได้ชัดเจน

การสลับแบบดั้งเดิมต้องใช้ตัวแปรจัดเก็บชั่วคราว อย่างไรก็ตาม การใช้อัลกอริทึมการสลับแบบ XOR ไม่จำเป็นต้องใช้พื้นที่จัดเก็บชั่วคราว อัลกอริทึมมีดังนี้: ^{[ 1 ] [ 2 ]}

X := Y XOR X ; // ทำการ XOR ค่าและเก็บผลลัพธ์ไว้ใน X Y := X XOR Y ; // ทำการ XOR ค่าและเก็บผลลัพธ์ไว้ใน Y X := Y XOR X ; // ทำการ XOR ค่าและเก็บผลลัพธ์ไว้ใน X

เนื่องจาก XOR เป็นการดำเนินการแบบสลับที่ได้ดังนั้น X XOR Y หรือ Y XOR X จึงสามารถใช้แทนกันได้ในสามบรรทัดข้างต้น โปรดทราบว่าในบางสถาปัตยกรรม ตัวถูกดำเนินการตัวแรกของคำสั่ง XOR จะระบุตำแหน่งเป้าหมายที่จะเก็บผลลัพธ์ของการดำเนินการ ซึ่งจะทำให้ไม่สามารถใช้แทนกันได้ โดยทั่วไปแล้วอัลกอริทึมนี้จะสอดคล้องกับ คำสั่ง รหัสเครื่อง สาม คำสั่ง ซึ่งแสดงด้วยรหัสเทียมและคำสั่งแอสเซมบลีที่สอดคล้องกันในสามแถวของตารางต่อไปนี้:

ในตัวอย่างโค้ดแอสเซมบลี System/370 ข้างต้น R1 และ R2 เป็นรีจิสเตอร์ ที่แยกจากกัน และXRการดำเนินการแต่ละครั้งจะเก็บผลลัพธ์ไว้ในรีจิสเตอร์ที่ระบุในอาร์กิวเมนต์แรก เมื่อใช้แอสเซมบลี x86 ค่า X และ Y จะอยู่ในรีจิสเตอร์ eax และ ebx (ตามลำดับ) และxorจะเก็บผลลัพธ์ของการดำเนินการไว้ในรีจิสเตอร์แรก (หมายเหตุ: x86 รองรับคำสั่ง XCHG ดังนั้นการใช้ XOR สามตัวจึงไม่มีความหมายในสถาปัตยกรรมนี้) เมื่อใช้แอสเซมบลี RISC-V ค่า X และ Y จะอยู่ในรีจิสเตอร์ x10 และ x11 และxorจะเก็บผลลัพธ์ของการดำเนินการไว้ในตัวถูกดำเนินการตัวแรก

อย่างไรก็ตาม ในเวอร์ชันหรือการใช้งานแบบรหัสเทียมหรือภาษาโปรแกรมระดับสูง อัลกอริทึมจะล้มเหลวหากxและyใช้ตำแหน่งจัดเก็บเดียวกัน เนื่องจากค่าที่เก็บไว้ในตำแหน่งนั้นจะถูกทำให้เป็นศูนย์โดยคำสั่ง XOR แรก และจะยังคงเป็นศูนย์ต่อไป มันจะไม่ถูก "สลับกับตัวเอง" ซึ่งไม่เหมือนกับกรณีที่xและyมีค่าเท่ากัน ปัญหาจะเกิดขึ้นเฉพาะเมื่อxและyใช้ตำแหน่งจัดเก็บเดียวกัน ซึ่งในกรณีนี้ค่าของพวกมันจะต้องเท่ากันอยู่แล้ว นั่นคือ ถ้าxและyใช้ตำแหน่งจัดเก็บเดียวกัน บรรทัดต่อไปนี้:

X := X XOR Y

ฟังก์ชันนี้จะกำหนดค่า xเป็นศูนย์ (เนื่องจากx = yดังนั้น X XOR Y จึงเป็นศูนย์) และกำหนดค่าyเป็นศูนย์ (เนื่องจากใช้พื้นที่จัดเก็บเดียวกัน) ทำให้xและyสูญเสียค่าเดิมไป

การดำเนินการไบนารี XOR บนสตริงบิตที่มีความยาวมีคุณสมบัติดังต่อไปนี้ (โดยที่หมายถึง XOR): ^{[ a ]}${\displaystyle N}$${\displaystyle \oplus }$

• L1. การสลับที่กันได้ :${\displaystyle A\oplus B=B\oplus A}$
• L2. การเชื่อมโยงความหมาย :${\displaystyle (A\oplus B)\oplus C=A\oplus (B\oplus C)}$
• L3. เอกลักษณ์มีอยู่จริง : มีสตริงบิต 0 (ความยาวN ) เช่นนั้นสำหรับทุกๆ${\displaystyle A\oplus 0=A}$${\displaystyle A}$
• L4.แต่ละองค์ประกอบเป็นอินเวอร์ส ของตัวเอง : สำหรับแต่ละ, .${\displaystyle A}$${\displaystyle A\oplus A=0}$

สมมติว่าเรามีรีจิสเตอร์สองตัวที่แตกต่างกันR1ดังR2แสดงในตารางด้านล่าง โดยมีค่าเริ่มต้นเป็นAและBตามลำดับ เราจะดำเนินการตามขั้นตอนด้านล่างตามลำดับ และลดทอนผลลัพธ์โดยใช้คุณสมบัติที่ระบุไว้ข้างต้น

ขั้นตอน	การดำเนินการ	ลงทะเบียน 1	ลงทะเบียน 2	การลดน้อยลง
0	ค่าเริ่มต้น	${\displaystyle A}$	${\displaystyle B}$	—
1	R1 := R1 XOR R2	${\displaystyle A\oplus B}$	${\displaystyle B}$	—
2	R2 := R1 XOR R2	${\displaystyle A\oplus B}$	${\displaystyle (A\oplus B)\oplus B=A\oplus (B\oplus B)}$${\displaystyle =A\oplus 0}$${\displaystyle =A}$	L2 L4 L3
3	R1 := R1 XOR R2	${\displaystyle (A\oplus B)\oplus A=(B\oplus A)\oplus A}$${\displaystyle =B\oplus (A\oplus A)}$${\displaystyle =B\oplus 0}$${\displaystyle =B}$	${\displaystyle \ A}$	L1 L2 L4 L3

เนื่องจาก XOR สามารถตีความได้ว่าเป็นการบวกเลขฐานสอง และคู่ของบิตสามารถตีความได้ว่าเป็นเวกเตอร์ในปริภูมิเวกเตอร์ สองมิติ เหนือฟิลด์ที่มีสององค์ประกอบดังนั้นขั้นตอนในอัลกอริธึมจึงสามารถตีความได้ว่าเป็นการคูณด้วยเมทริกซ์ 2×2 เหนือฟิลด์ที่มีสององค์ประกอบ เพื่อความง่าย ให้สมมติในเบื้องต้นว่าxและyแต่ละตัวเป็นบิตเดี่ยว ไม่ใช่เวกเตอร์บิต

ตัวอย่างเช่น ขั้นตอน:

X := X XOR Y

ซึ่งมีความหมายโดยนัยเช่นกัน:

Y := Y

สอดคล้องกับเมทริกซ์ดังนี้ ${\displaystyle \left({\begin{smallmatrix}1&1\\0&1\end{smallmatrix}}\right)}$

${\displaystyle {\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}x+y\\y\end{pmatrix}}.}$

ลำดับการดำเนินการจึงแสดงได้ดังนี้:

${\displaystyle {\begin{pmatrix}1&1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$

(เนื่องจากทำงานกับค่าไบนารี) ซึ่งแสดงเมทริกซ์พื้นฐานของการสลับสองแถว (หรือสองคอลัมน์) ในแง่ของการเคลื่อนตัว (การเฉือน) ของการเพิ่มองค์ประกอบหนึ่งไปยังอีกองค์ประกอบหนึ่ง ${\displaystyle 1+1=0}$

เพื่อให้ครอบคลุมกรณีที่ X และ Y ไม่ใช่บิตเดี่ยว แต่เป็นเวกเตอร์บิตที่มีความยาวnเมทริกซ์ 2×2 เหล่านี้จะถูกแทนที่ด้วยเมทริกซ์บล็อก2n × 2n เช่น${\displaystyle \left({\begin{smallmatrix}I_{n}&I_{n}\\0&I_{n}\end{smallmatrix}}\right).}$

เมทริกซ์เหล่านี้ทำงานกับค่าไม่ใช่ตัวแปร (ที่มีตำแหน่งจัดเก็บ) ดังนั้นการตีความนี้จึงละเลยประเด็นเรื่องตำแหน่งจัดเก็บและปัญหาที่ตัวแปรทั้งสองใช้ตำแหน่งจัดเก็บเดียวกัน

ฟังก์ชัน ภาษาCที่ใช้หลักการสลับค่าแบบ XOR:

void xor_swap ( int * x , int * y ) { if ( x == y ) return ; * x ^= * y ; * y ^= * x ; * x ^= * y ; }

โค้ดจะตรวจสอบก่อนว่าที่อยู่แตกต่างกันหรือไม่ และใช้เงื่อนไขตรวจสอบเพื่อออกจากฟังก์ชันก่อนกำหนดหากที่อยู่เท่ากัน หากไม่มีการตรวจสอบนี้ หากที่อยู่เท่ากัน อัลกอริทึมจะพับค่าเป็นสามเท่า*x ^= *xซึ่งส่งผลให้ได้ผลลัพธ์เป็นศูนย์

ในสถาปัตยกรรม CPU สมัยใหม่ เทคนิค XOR อาจช้ากว่าการใช้ตัวแปรชั่วคราวเพื่อทำการสลับ อย่างน้อยใน CPU x86 รุ่นล่าสุด ทั้งของ AMD และ Intel การย้ายระหว่างรีจิสเตอร์เป็นประจำจะไม่ทำให้เกิดความล่าช้า (เรียกว่าการกำจัด MOV) แม้ว่าจะไม่มีรีจิสเตอร์ทางสถาปัตยกรรมใด ๆ ที่พร้อมใช้งานXCHGคำสั่งก็จะเร็วอย่างน้อยเท่ากับ XOR สามครั้งรวมกัน อีกเหตุผลหนึ่งคือ CPU สมัยใหม่พยายามที่จะดำเนินการคำสั่งแบบขนานผ่านทางไปป์ไลน์คำสั่งในเทคนิค XOR อินพุตของแต่ละการดำเนินการขึ้นอยู่กับผลลัพธ์ของการดำเนินการก่อนหน้า ดังนั้นจึงต้องดำเนินการตามลำดับอย่างเคร่งครัด ซึ่งทำให้ประโยชน์ของการทำงานแบบขนานในระดับคำสั่งหมดไป^{[ 3 ]}

การสลับค่าแบบ XOR นั้นมีความซับซ้อนในทางปฏิบัติเนื่องจากปัญหาการใช้ชื่อซ้ำ (aliasing ) หากพยายามสลับค่าในตำแหน่งใดตำแหน่งหนึ่งกับตัวมันเอง ผลลัพธ์ที่ได้คือตำแหน่งนั้นจะถูกตั้งค่าเป็นศูนย์และค่าของมันจะหายไป ดังนั้น การสลับค่าแบบ XOR จึงไม่ควรใช้โดยไม่พิจารณาอย่างรอบคอบในภาษาโปรแกรมระดับสูงหากสามารถใช้ชื่อซ้ำได้ ปัญหานี้จะไม่เกิดขึ้นหากใช้วิธีการนี้ในภาษาแอสเซมบลีเพื่อสลับค่าในรีจิสเตอร์สองตัว

ปัญหาที่คล้ายกันนี้เกิดขึ้นกับการเรียกใช้ฟังก์ชันโดยระบุชื่อดังเช่นในJensen's Deviceที่การสลับค่าiและA[i]การใช้ตัวแปรชั่วคราวทำให้ได้ผลลัพธ์ที่ไม่ถูกต้องเนื่องจากอาร์กิวเมนต์มีความสัมพันธ์กัน การสลับค่าจะtemp = i; i = A[i]; A[i] = tempเปลี่ยนค่าของiในคำสั่งที่สอง ซึ่งส่งผลให้iค่าของA[i]ในคำสั่งที่สาม ไม่ถูกต้อง

หลักการพื้นฐานของอัลกอริธึมการสลับ XOR สามารถนำไปใช้กับการดำเนินการใดๆ ที่ตรงตามเกณฑ์ L1 ถึง L4 ข้างต้นได้ การแทนที่ XOR ด้วยการบวกและการลบจะให้สูตรที่แตกต่างกันเล็กน้อย แต่โดยส่วนใหญ่แล้วเทียบเท่ากัน ตัวอย่างเช่น: ^{[ 4 ]}

void add_swap ( unsigned int * x , unsigned int * y ) { * x = * x + * y ; * y = * x - * y ; * x = * x - * y ; }

แตกต่างจากการสลับค่าแบบ XOR รูปแบบนี้ต้องการให้โปรเซสเซอร์หรือภาษาโปรแกรมพื้นฐานใช้วิธีการ เช่นเลขคณิตแบบโมดูลาร์หรือบิ๊กนัมเพื่อรับประกันว่าการคำนวณX + Yจะไม่ก่อให้เกิดข้อผิดพลาดเนื่องจากจำนวนเต็มเกินขีดจำกัดดังนั้นจึงพบเห็นได้น้อยกว่าการสลับค่าแบบ XOR ในทางปฏิบัติ

อย่างไรก็ตาม การนำวิธีการAddSwapข้างต้นไปใช้ในภาษาโปรแกรม C นั้นใช้งานได้เสมอ แม้ในกรณีที่จำนวนเต็มเกิดการล้น (integer overflow) เนื่องจากตามมาตรฐานของภาษา C การบวกและการลบจำนวนเต็มที่ไม่มีเครื่องหมายเป็นไปตามกฎของเลขคณิตแบบโมดูลาร์กล่าวคือ ดำเนินการในกลุ่มวัฏจักร โดยที่คือจำนวนบิตของอันที่จริง ความถูกต้องของอัลกอริทึมมาจากการที่สูตรและเป็นจริงในกลุ่มอาเบเลียน ใดๆ สิ่งนี้เป็นการสรุปการพิสูจน์สำหรับอัลกอริทึมการสลับ XOR: XOR เป็นทั้งการบวกและการลบในกลุ่มอาเบเลียน(ซึ่งเป็นผลรวมโดยตรงของsสำเนาของ) ${\displaystyle \mathbb {Z} /2^{s}\mathbb {Z} }$${\displaystyle s}$unsigned int${\displaystyle (x+y)-y=x}$${\displaystyle (x+y)-((x+y)-y)=y}$${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{s}}$${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

หลักการนี้ใช้ไม่ได้กับsigned intประเภท (ค่าเริ่มต้นสำหรับint) การโอเวอร์โฟลว์ของจำนวนเต็มที่มีเครื่องหมายเป็นพฤติกรรมที่ไม่กำหนดในภาษา C ดังนั้นมาตรฐานจึงไม่รับประกันการคำนวณแบบโมดูลาร์ ซึ่งอาจนำไปสู่ผลลัพธ์ที่ไม่ถูกต้อง

ลำดับการดำเนินการในAddSwapสามารถแสดงได้โดยใช้การคูณเมทริกซ์ดังนี้:

${\displaystyle {\begin{pmatrix}1&-1\\0&1\end{pmatrix}}{\begin{pmatrix}1&0\\1&-1\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}={\begin{pmatrix}0&1\\1&0\end{pmatrix}}}$

ในสถาปัตยกรรมที่ไม่มีคำสั่งสลับเฉพาะ เนื่องจากหลีกเลี่ยงรีจิสเตอร์ชั่วคราวเพิ่มเติม จึงจำเป็นต้องใช้อัลกอริธึมการสลับแบบ XOR เพื่อ การจัดสรรรีจิสเตอร์ ที่เหมาะสมที่สุด ซึ่งมีความสำคัญอย่างยิ่งสำหรับคอมไพเลอร์ที่ใช้รูปแบบการกำหนดค่าเดี่ยวแบบคงที่สำหรับการจัดสรรรีจิสเตอร์ คอมไพเลอร์เหล่านี้บางครั้งสร้างโปรแกรมที่ต้องสลับรีจิสเตอร์สองตัวเมื่อไม่มีรีจิสเตอร์ว่าง อัลกอริธึมการสลับแบบ XOR หลีกเลี่ยงความจำเป็นในการสำรองรีจิสเตอร์เพิ่มเติมหรือการเขียนรีจิสเตอร์ใดๆ ลงในหน่วยความจำหลัก^{[ 5 ]}รูปแบบการบวก/ลบก็สามารถใช้เพื่อวัตถุประสงค์เดียวกันได้เช่นกัน^{[ 6 ]}

วิธีการจัดสรรรีจิสเตอร์นี้มีความเกี่ยวข้องอย่างยิ่งกับ คอมไพเลอร์เชเดอร์ GPUบนสถาปัตยกรรม GPU สมัยใหม่ การกระจายตัวแปรมีค่าใช้จ่ายสูงเนื่องจากแบนด์วิดท์หน่วยความจำ ที่จำกัด และความหน่วงของหน่วยความจำสูง ในขณะที่การจำกัดการใช้รีจิสเตอร์สามารถปรับปรุงประสิทธิภาพได้เนื่องจากการแบ่งพาร์ติชันไฟล์รีจิสเตอร์ แบบไดนามิก ดังนั้นอัลกอริทึมการสลับ XOR จึงจำเป็นสำหรับคอมไพเลอร์ GPU บางตัว^{[ 7 ]}

• ความแตกต่างแบบสมมาตร
• รายการเชื่อมโยง XOR
• รหัสลับไฟสเตล (อัลกอริธึมการสลับ XOR เป็นรูปแบบที่ลดทอนลงของรหัสลับไฟสเตล)