تنفيذ عملية XOR بدون معامل XOR

السلام عليكم

سنتحدث في هذا المقال عن كيفية تطبيق عملية xor بدون استخدام معامل xor، بل فقط باستخدام العمليات الأساسية and، or، not (للتمويه مثلاً :ph34r:). ستفهم أيضاً كيف يمكنك اشتقاق أي عملية باستخدام هذه العمليات الأساسية.

ملاحظة: سأستخدم رموز C لهذه العمليات:

and    &or     |not    ~

لو نظرت لجدول الصدق لعملية xor سترى التالي:

a | b | a ^ b
---+---+-------
 0 | 0 | 0
 0 | 1 | 1
 1 | 0 | 1
 1 | 1 | 0

العملية تعطي 1 في حالتين، عندما تكون "(a صفر و b واحد) أو (عندما تكون a واحد و b صفر)". بدل كل معمل قيمته صفر بنفي not والمعامل الذي قيمته واحد أبقه كما هو ثم أربطهما بـand:

a | b | a ^ b |
---+---+-------+---------
 0 | 0 | 0     |
 0 | 1 | 1     | ~a &  b
 1 | 0 | 1     |  a & ~b
 1 | 1 | 0     |

الآن ادمج تلك المعادلتين بـor:

(~a & b) | (a & ~b)

أو بالعربي "(a صفر و b واحد) أو (عندما تكون a واحد و b صفر)".

هكذا حصلت على عملية xor مكافئة :o، لو جربتها ستعطي نفس جدول الصواب:

a | b | a ^ b | (~a & b) | (a & ~b)
---+---+-------+---------------------
 0 | 0 | 0     | 0
 0 | 1 | 1     | 1
 1 | 0 | 1     | 1
 1 | 1 | 0     | 0

الخطوات مرة أخرى:

1, خذ فقط القيم التي تعطي 1 في جدول الصدق.

2. بدل كل صفر بنفي not ثم ادمج القيم بـand.

3. ادمج المعادلات الناتجة بـor.

هذه الطريقة نفس الطريقة المستخدمة لإستنتاج أي عملية منطقية، لكنها قد تعطي معادلات تحتاج للتبسيط، يمكنك استخدام قوانين تبسيط المعادلات المنقطية أو استخدام أحد الأدوات مثل wolfram alpha، (مثال لتبسيط ~~a إلى a).

اختبار صغير بالـc (لاحاجة للتحقق طالما أن جدول الصدق مطابق):

#include <time.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <inttypes.h>

/* flat xor operation */
static uint32_t
flat_xor(uint32_t a, uint32_t b)
{
  return (~a & b) | (a & ~b);
}

/* generate 32-bit random number, rand()
 * generates only up to RAND_MAX */
static uint32_t
rand32(void)
{
  uint32_t r = 0;

  r |= (rand() % 0xff);
  r |= (rand() % 0xff) << 8;
  r |= (rand() % 0xff) << 16;
  r |= (rand() % 0xff) << 24;

  return r;
}

/* simple test case */
int
main(int argc, char **argv)
{
  uint32_t a;
  uint32_t b;
  uint32_t i;

  srand(time(NULL));

  /* assert that a ^ b == flat_xor(a, b) */
  for( i = 0 ; i < 1000 ; i++ )
  {
    a = rand32();
    b = rand32();

    assert( (a ^ b) == flat_xor(a, b) );
  }

  return 0;
}

تنفيذ عملية XOR بدون معامل XOR

مواضيع مشابهة