كيف يعمل مبادلة متغيرات XOR؟

Question

هل يمكن لأحد أن يشرح لي كيف يعمل تبديل XOR لمتغيرين بدون متغير مؤقت؟

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

أنا أفهم ما يفعله، ولكن هل يمكن لأي شخص أن يشرح لي المنطق الذي يعمل به؟

Answer 1

ويمكنك أن ترى كيف يعمل عن طريق القيام استبدال:

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

واستبدال،

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

ولأن XOR هو النقابي تماما وتبادلي:

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

ومنذ x xor x == 0 لأي س،

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

ومنذ x xor 0 == x لأي س،

y2 = x0
x2 = y0

وتتم المبادلة.

Answer 2

لقد شرحها أشخاص آخرون، والآن أريد أن أشرح لماذا كانت فكرة جيدة، لكنها ليست كذلك الآن.

في الماضي، عندما كان لدينا وحدات معالجة مركزية بسيطة ذات دورة واحدة أو وحدات معالجة مركزية متعددة الدورات، كان من الأرخص استخدام هذه الخدعة لتجنب إلغاء مرجعيات الذاكرة المكلفة أو سكب السجلات على المكدس.ومع ذلك، لدينا الآن وحدات معالجة مركزية ذات خطوط أنابيب ضخمة بدلاً من ذلك.تراوحت خطوط أنابيب P4 من 20 إلى 31 (أو نحو ذلك) مرحلة في مساراتها، حيث يمكن أن يؤدي أي اعتماد بين القراءة والكتابة إلى السجل إلى توقف الأمر برمته.تحتوي مبادلة xor على بعض التبعيات الثقيلة جدًا بين A وB والتي لا تهم في الواقع على الإطلاق ولكنها تعطل خط الأنابيب في الممارسة العملية.يتسبب خط الأنابيب المتوقف في مسار تعليمات برمجية بطيء، وإذا كانت هذه المبادلة موجودة في حلقتك الداخلية، فسوف تتحرك ببطء شديد.

في الممارسة العامة، يمكن للمترجم الخاص بك معرفة ما تريد فعله حقًا عند إجراء مبادلة مع متغير مؤقت ويمكنه تجميعه في تعليمة XCHG واحدة.استخدام المبادلة xor يجعل من الصعب على المترجم تخمين نيتك، وبالتالي أقل احتمالية لتحسينها بشكل صحيح.ناهيك عن صيانة الكود وما إلى ذلك.

Answer 3

وأنا أحب التفكير في الأمر بوضوح بدلا من عدديا.

ودعونا نقول أن تبدأ مع x = 11 و y = 5 في ثنائي (وانا ذاهب الى استخدام افتراضية آلة 4 بت)، وهنا x و y

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

والآن لي، XOR هو عملية قلب وفعل ذلك مرتين هو مرآة:

     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!

Answer 4

إليك واحدة ينبغي أن تكون أسهل قليلًا في التعامل معها:

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

الآن، يمكن للمرء أن يفهم خدعة XOR بسهولة أكبر من خلال فهم ذلك ^ يمكن أن يعتقد من + أو -.نحن فقط:

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

, ، لذا:

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

Answer 5

والسبب أنه يعمل لأن XOR لا تفقد المعلومات. هل يمكن أن تفعل الشيء نفسه مع الجمع والطرح العادية إذا كنت قد تجاهل تجاوز. على سبيل المثال، إذا كان المتغير زوج A، B يحتوي أصلا على القيم 1،2، هل يمكن مقايضتهم مثل هذا:

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

وبالمناسبة هناك خدعة قديمة لترميز قائمة مرتبطة 2-الطريقة في "المؤشر" واحد. لنفترض لديك قائمة من كتل الذاكرة في عناوين A، B، C. والكلمة الأولى في كل كتلة هو على التوالي:

 // 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

إذا كان لديك الوصول إلى منع A، فهو يوفر لك عنوان B. للوصول إلى C، كنت تأخذ من "المؤشر" في B وطرح A، وهلم جرا. وهي تعمل فقط كذلك إلى الوراء. لتشغيل على طول القائمة، تحتاج إلى الحفاظ على مؤشرات إلى كتلتين متتالية. بالطبع كنت ستستخدم XOR بدلا من إضافة / subtration، لذلك كنت لا داعي للقلق حول تجاوز.

هل يمكن تمديد هذه ل"شبكة مرتبطة" إذا أردت الحصول على بعض المتعة.

Answer 6

ومعظم الناس سوف مبادلة اثنين من المتغيرات x و y باستخدام متغير مؤقت، مثل هذا:

tmp = x
x = y
y = tmp

وإليك خدعة البرمجة أنيق لمبادلة قيمتين دون الحاجة إلى درجة الحرارة:

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

ومزيد من التفاصيل في مبادلة اثنين من المتغيرات باستخدام XOR

<اقتباس فقرة>   

في السطر 1 نحن الجمع بين x و y (باستخدام XOR) للحصول على هذا "مختلطة" ونقوم بتخزين مرة أخرى في العاشر. XOR هو وسيلة رائعة لحفظ المعلومات، لأنك يمكن إزالته عن طريق القيام على XOR مرة أخرى.

     

في خط 2. نحن XOR هجين مع ذ، الذي يلغي كل المعلومات ذ، وترك لنا فقط مع x. نحن نوفر هذه النتيجة مرة أخرى في ص، وحتى الآن فقد تبادلت.

     

في السطر الأخير، الأشعة لا تزال لديه قيمة الهجين. نحن XOR ذلك مرة أخرى مع ذ (الآن مع القيمة الأصلية س) لإزالة كل آثار العاشر من الهجين. هذا يتركنا مع ذ، والمبادلة كاملة!

---

<اقتباس فقرة>   

والكمبيوتر لديها في الواقع الضمني "مؤقت" متغير يقوم بتخزين نتائج المتوسطة قبل كتابتها مرة أخرى إلى السجل. على سبيل المثال، إذا قمت بإضافة 3 إلى سجل (في شبة الكود لغة آلة):

ADD 3 A // add 3 to register A

<اقتباس فقرة>   

ووALU (وحدة المنطق الحسابي) هو في الواقع ما ينفذ تعليمات 3 + A. فإنه يأخذ المدخلات (3، A) ويخلق نتيجة لذلك (3 + A)، التي CPU ثم متاجر العودة إلى تسجيل الأصلي. لذلك، استخدمنا ALU الفضاء الصفر كما مؤقت قبل كان لدينا الجواب النهائي.

     

ونحن نأخذ بيانات مؤقتة ضمنية على ALU للمنح، ولكن دائما هناك. بطريقة مماثلة، يمكن للALU إعادة المتوسطة نتيجة للXOR في حالة س = س XOR ذ، وعند هذه النقطة وحدة المعالجة المركزية يخزنها في السجل العاشر الأصلي.

     

ولأننا غير معتادين على التفكير في الفقراء، ALU المهملة، وتبادل XOR يبدو السحري لأنه لم يكن لديك متغير مؤقت صريح. بعض الآلات لديها 1-خطوة الصرف XCHG تعليمات لمبادلة سجلين.

Answer 7

VonC ديه ذلك الحق، انها خدعة رياضية نظيفة . تخيل 4 كلمات قليلا ونرى ما اذا كان هذا يساعد.

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 8

هناك ثلاث خطوات في نهج XOR:

أ' = أ XOR ب (1)
ب' = أ' XOR ب (2)
أ" = أ" XOR ب" (3)

لفهم لماذا هذا يعمل أولا لاحظ أن:

1. لن ينتج XOR 1 إلا إذا كان أحد معاملاته بالضبط هو 1، والآخر صفر؛
2. XOR هو تبادلي لذا فإن XOR b = b XOR a;
3. XOR هو ترابطي لذلك (أ XOR ب) XOR ج = أ XOR (ب XOR ج)؛و
4. XOR a = 0 (يجب أن يكون هذا واضحًا من التعريف الموجود في 1 فوق)

بعد الخطوة (1)، سيكون التمثيل الثنائي لـ a بت واحد فقط في مواضع البت حيث يكون لـ a وb بتات متعارضة.وهذا إما (ak=1, bk=0) أو (ak=0, bk=1).الآن عندما نقوم بالاستبدال في الخطوة (2) نحصل على:

ب' = (أ XOR ب) XOR ب
= XOR (b XOR b) لأن XOR ترابطي
= XOR 0 بسبب [4] أعلاه
= بسبب تعريف XOR (انظر 1 فوق)

الآن يمكننا التعويض في الخطوة (3):

أ" = (أ XOR ب) XOR أ
= (b XOR a) XOR a لأن XOR تبادلية
= b XOR (a XOR a) لأن XOR ترابطي
= ب XOR 0 بسبب [4] أعلاه
= b بسبب تعريف XOR (انظر 1 فوق)

مزيد من المعلومات التفصيلية هنا:ضرورية وكافية

Answer 9

وكملاحظة جانبية I اختراع هذه العجلة قبل عدة سنوات بشكل مستقل في شكل مبادلة صحيحة عن طريق القيام:

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

(وهذا مذكور أعلاه في مهمة صعبة لقراءة الطريق)،

ونفس المنطق ينطبق بالضبط على مقايضة XOR: أ ^ ب ^ ب = لو^ ب ^ أ = أ. منذ XOR غير تبادلي، س ^ س = 0 و x ^ 0 = س، وهذا من السهل جدا أن نرى منذ

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

و

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

ويساعد هذا الأمل. وقد تم بالفعل منح هذا التفسير ... ولكن ليس واضح جدا المنظمة البحرية الدولية.