حيل التعامل مع البِتّات (Bit Manipulation Tricks)

سنفترض وجود المتغيرين التاليين:

int x;       // some non-negative integer
int k;       // 0-based bit index (0 = least significant bit)

وسنستخدم أقنعة (masks) مثل 1 << k، والتي يكون فيها البِت رقم k فقط مساويًا لـ1.

فحص ما إذا كان البِت k يساوي 1

bool isSet = (x >> k) & 1;

• x >> k → إزاحة لليمين بحيث ينتقل البِت رقم k إلى أقصى اليمين.
• (x >> k) & 1 → تُبقي البِت الأيمن فقط وتصفّر باقي البِتّات.
• الناتج يكون 0 أو 1، وهو يعادل false أو true منطقيًا.

أمثلة

افحص ما إذا كان البِت رقم 1 في x مُعينًا (يساوي 1).

int x = 10;     // 10 = 1010 (in binary)
int k = 1;

bool isSet = (x >> 1) & 1; // 1010 >> 1 = 101;  101 & 1 = 1 (true)

معطى عددان n وk، اكتب دالة تحدد ما إذا كان البِت رقم k في n مساويًا لـ1.

bool kthBitIsSet(int n, int k) {
    return (n >> k) && 1;
}

ضبط البِت رقم k إلى 1

x |= (1 << k);

• العامل | يعيّن البِت إلى 1 إذا كان على الأقل أحد الطرفين يحتوي 1.
• بهذا نجبر البِت رقم k أن يصبح 1، بينما تبقى باقي البِتّات كما هي.

مثال

int x = 4;      // 0100
x |= (1 << 0);  // 0100 | 0001 = 0101 (5)

تصفير البِت رقم k (جعله 0)

x &= ~(1 << k);

• 1 << k → قناع فيه البِت رقم k يساوي 1.
• ~(1 << k) → قناع فيه البِت رقم k يساوي 0، وجميع البِتّات الأخرى تساوي 1.
• إجراء & مع هذا القناع يقوم بتصفير البِت رقم k فقط.

مثال

int x = 13;         // 1101
x &= ~(1 << 2);     // ~(0100) = ...1011
                    // 1101 & 1011 = 1001 (9)

الآن البِت رقم 2 أصبح 0.

قلب (تبديل) البِت رقم k

x ^= (1 << k);

• العامل ^ (XOR) يقلب البِت عندما يكون القناع فيه 1:

  • 0 ^ 1 = 1
  • 1 ^ 1 = 0

مثال

int x = 5;     // 0101
x ^= (1 << 2); // 0101 ^ 0100 = 0001 (1)

البِت رقم 2 كان 1 → أصبح الآن 0.

إزالة أقل بِت معيّن (أقل 1 من اليمين)

هذه حيلة مشهورة جدًّا:

x = x & (x - 1);

هذا السطر يزيل (يُصفّر) أقل بِت معيّن (أول 1 من جهة اليمين) في x.

لماذا تعمل هذه الحيلة؟

فكّر ماذا يحدث للبِتّات عندما نطرح 1:

• عند تنفيذ x - 1، نمشي من اليمين حتى نجد أول بِت قيمته 1.
• هذا البِت الأقل (أقرب 1 لليمين) يتحوّل إلى 0.
• كل البِتّات التي على يمينه (والتي كانت 0) تتحوّل إلى 1 (بسبب الاقتراض في الطرح).

إذًا حول أقل بِت معيّن، النمط يكون بهذا الشكل:

x:       .... 1 0 0 0 0
x - 1:   .... 0 1 1 1 1

عند إجراء AND:

x        = .... 1 0 0 0 0
x - 1    = .... 0 1 1 1 1
-------------------------
x&(x-1)  = .... 0 0 0 0 0

• أقل بِت معيّن يصبح 0 لأنه 1 & 0.
• كل البِتّات التي على يمينه كانت 0 في x، ومع أي قيمة في x - 1 تعطي 0 & something = 0.
• كل البِتّات التي على يساره لا تتأثر، لأن الطرح لم يغيّرها؛ أي أن قيمتها في x وx - 1 متطابقة، وبالتالي تبقى كما هي بعد AND.

لذلك x & (x - 1) تساوي قيمة x نفسها لكن مع أقل بِت معيّن مصفّرًا.

مثال

x           = 12 = 1100
x - 1       = 11 = 1011
x & (x - 1) =  8 = 1000

إذًا قمنا بإزالة أقل بِت معيّن (البِت رقم 2).

فحص ما إذا كان x قوة للعدد 2

سنفترض أن x عدد موجب، ونستخدم الحيلة السابقة:

bool isPowerOfTwo = (x & (x - 1)) == 0;

لماذا تعمل هذه الحيلة؟

• العدد الذي هو قوة للعدد 2 في الثنائي (1, 10, 100, 1000, …) يحتوي بِتًا واحدًا فقط معيّنًا.
• عند تنفيذ x & (x - 1) نقوم بإزالة أقل بِت معيّن.
• إذا كان هناك بِت واحد فقط معيّن، فبعد إزالة هذا البِت تصبح القيمة 0.

إذًا:

• x & (x - 1) == 0 ⇔ x لديه بِت واحد معيّن فقط (أي قوة للعدد 2).

أمثلة

• x = 8 (1000) → x & (x-1) = 1000 & 0111 = 0000 → قوة للعدد 2.
• x = 12 (1100) → x & (x-1) = 1100 & 1011 = 1000 → ليست 0 → ليس قوة للعدد 2.

الحصول على أقل بِت معيّن فقط

int lowest = x & -x;

هنا -x هو المتمّم الثنائي (two’s complement) للعدد x.

الفكرة:

• التعبير x & -x يعزل أقل بِت معيّن (أول 1 من جهة اليمين) ويصفّر جميع البِتّات الأخرى.

مثال

x                = 12 = ...00001100
-x (two's complement) = ...11110100
x & -x                = ...00000100 = 4

أقل بِت معيّن في x يمثّل القيمة 4 (أي البِت رقم 2).

ملخص سريع

• فحص البِت رقم k: isSet = (x >> k) & 1;
• ضبط البِت رقم k إلى 1: x |= (1 << k);
• تصفير البِت رقم k: x &= ~(1 << k);
• قلب (تبديل) البِت رقم k: x ^= (1 << k);
• إزالة أقل بِت معيّن: x &= (x - 1);
• فحص إذا كان x قوة للعدد 2: x > 0 && (x & (x - 1)) == 0
• الحصول على أقل بِت معيّن فقط: lowest = x & -x;

هذه هي أهم وأشهر حيل التعامل مع البِتّات (bit manipulation) في البرمجة.