كيف يمكنك تنفيذ XOR باستخدام +-*/؟

Question

كيف يمكن تنفيذ عملية XOR (على مدخلين 32 بت) باستخدام العمليات الحسابية الأساسية فقط؟هل يجب عليك القيام بذلك بطريقة البت بعد القسمة على كل قوة 2 على التوالي، أم أن هناك اختصارًا؟لا أهتم بسرعة التنفيذ بقدر اهتمامي بأبسط وأقصر كود.

يحرر:هذا ليس واجبًا منزليًا، ولكنه لغز تم طرحه على أ hacker.org.الهدف هو تنفيذ XOR على جهاز ظاهري قائم على المكدس مع عمليات محدودة للغاية (على غرار com.brainfuck اللغة ونعم - لا يوجد تحول أو تعديل).يعد استخدام هذا الجهاز الافتراضي هو الجزء الصعب، على الرغم من أنه أصبح أسهل بالطبع بفضل خوارزمية قصيرة وبسيطة.

على الرغم من أن حل FryGuy ذكي، إلا أنني سأضطر إلى اتباع الحل المثالي الأصلي (على غرار حل litb) نظرًا لصعوبة استخدام المقارنات أيضًا في تلك البيئة.

Answer 1

أنا آسف لأنني أعرف فقط ما هو مستقيم في الرأس:

uint32_t mod_op(uint32_t a, uint32_t b) {
    uint32_t int_div = a / b;
    return a - (b * int_div);
}

uint32_t xor_op(uint32_t a, uint32_t b) {
    uint32_t n = 1u;
    uint32_t result = 0u;
    while(a != 0 || b != 0) {
        // or just: result += n * mod_op(a - b, 2);
        if(mod_op(a, 2) != mod_op(b, 2)) {
            result += n;
        }
        a /= 2;
        b /= 2;
        n *= 2;
    }
    return result;
}

يمكن استخدام البديل الموجود في التعليقات بدلاً من if لتجنب التفرع.ولكن مرة أخرى، الحل ليس سريعًا تمامًا ويجعل الأمر يبدو غريبًا :)

Answer 2

سأفعل ذلك بالطريقة البسيطة:

uint xor(uint a, uint b):    

uint ret = 0;
uint fact = 0x80000000;
while (fact > 0)
{
    if ((a >= fact || b >= fact) && (a < fact || b < fact))
        ret += fact;

    if (a >= fact)
        a -= fact;
    if (b >= fact)
        b -= fact;

    fact /= 2;
}
return ret;

قد تكون هناك طريقة أسهل، لكني لا أعرف واحدة.

Answer 3

لا أعرف ما إذا كان هذا يبطل المغزى من سؤالك، ولكن يمكنك تنفيذ XOR باستخدام AND وOR وNOT، على النحو التالي:

uint xor(uint a, uint b) {
   return (a | b) & ~(a & b);
}

في اللغة الإنجليزية، هذا يعني "a أو b، ولكن ليس a وb"، والذي يتوافق بدقة مع تعريف XOR.

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

Answer 4

يكون الأمر أسهل إذا كان لديك "و" لأنه

أ أو ب = أ + ب - (أ و ب)

أ XOR ب = أ + ب - 2(أ و ب)

int customxor(int a, int b)
{
    return a + b - 2*(a & b);
}