Coding Interview Prep · درس

العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات

راجِع العوامل الستة على مستوى البت باستخدام جداول الحقيقة وأمثلة Python، وافهم علاقة الإزاحتين اليسرى واليمنى بالضرب والقسمة على اثنين.

العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.

أهمية معالجة البتات

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

تتمتع أعداد Python الصحيحة بدقة غير محدودة — إذ يمكن أن تكبر بقدر ما تسمح به الذاكرة — لكن عمليات البتات تتبع دائمًا دلالات المتمّم الثنائي القياسية على مستوى العتاد. وتعمل العوامل الستة جميعها على التمثيلات الثنائية للأعداد الصحيحة بتًا بتًا.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

عامل AND: استخدام أقنعة البتات

يعطي عامل AND (&) الناتج 1 فقط عندما يكون كلا البتين في المدخل 1. ويُستخدم أساسًا في التقنيع: أي تحديد بتات معينة من عدد مع تصفير جميع البتات الأخرى. للتحقق مما إذا كان البت k مفعّلًا في العدد n، قيّموا n & (1 << k) — فإذا كان الناتج غير صفري، فإن البت k يساوي 1.

يُستخدم AND أيضًا في إلغاء تفعيل أدنى بت مفعّل: إذ تزيل n & (n - 1) بت 1 الموجود في أقصى اليمين. ويُستخدم ذلك لعدّ البتات المفعّلة بكفاءة، وللتحقق مما إذا كان العدد قوة للعدد اثنين (فقوة العدد اثنين تحتوي على بت مفعّل واحد بالضبط، ولذلك n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

عامل OR: تفعيل البتات

يعطي عامل OR (|) الناتج 1 إذا كان أحد بتّي الإدخال على الأقل يساوي 1. ويُستخدم أساسًا في تفعيل بت محدد إلى 1 من دون التأثير في البتات الأخرى. لتفعيل البت k في العدد n، استخدموا n | (1 << k). يؤدي الرقم 1 بعد إزاحته إلى الموضع k إلى تفعيل ذلك البت؛ بينما تبقى جميع البتات الأخرى دون تغيير، لأن إجراء OR لأي قيمة مع 0 يُبقيها كما هي.

يُستخدم OR أيضًا في دمج الأعلام: فإذا مثّلتم أعلام الميزات ببتات منفردة، فبإمكانكم تفعيل عدة أعلام باستخدام OR. فعلى سبيل المثال، يدمج READ | WRITE | EXECUTE ثلاثة بتات للصلاحيات في عدد صحيح واحد.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

عامل XOR: التبديل واكتشاف الاختلاف

يعطي عامل XOR (^) الناتج 1 عندما تختلف بتات الإدخال. ولـ XOR ثلاث خصائص جبرية قوية: a ^ a = 0 (تلغي المدخلات المتطابقة بعضها بعضًا)، وa ^ 0 = a (الصفر هو العنصر المحايد)، كما أن XOR تبادلي وتجميعي. وتجعل هذه الخصائص XOR الأداة الأساسية للعثور على العناصر الفريدة.

يُستخدم XOR أيضًا في تبديل بت محدد: إذ يقلب n ^ (1 << k) البت k مع إبقاء البتات الأخرى دون تغيير. فإذا كان البت k يساوي 0، أصبح 1؛ وإذا كان يساوي 1، أصبح 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

عامل NOT والمتمّم الثنائي

يعكس عامل NOT (~) جميع البتات. في Python، يساوي ~n القيمة -(n+1) بسبب استخدام تمثيل المتمّم الثنائي. وقد يفاجئ ذلك كثيرًا من الأشخاص: إذ إن ~5 = -6، وليس 0b11111010 المتوقع ظاهريًا. تتمتع أعداد Python بدقة غير محدودة، ولذلك يؤدي قلب جميع بتات عدد موجب إلى نتيجة سالبة وفقًا للمتمّم الثنائي.

عمليًا، نادرًا ما تستخدمون ~ وحده في Python لمعالجة البتات. وبدلًا من ذلك، استخدموه مع AND لإلغاء تفعيل بتات محددة، أو احسبوا ~n & mask حيث يحدّ القناع mask العرض إلى عدد محدد من البتات (مثل & 0xFFFFFFFF لعدد من 32 بتًا).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

الإزاحة إلى اليسار: الضرب في قوى العدد اثنين

ينقل عامل الإزاحة إلى اليسار (<<) جميع البتات إلى اليسار بمقدار k من المواضع، ويملأ المواضع الفارغة على اليمين بأصفار. وهذا يكافئ الضرب في 2^k. تؤدي الإزاحة إلى اليسار بمقدار 1 إلى مضاعفة القيمة، بينما يؤدي إزاحتها بمقدار k إلى ضربها في 2^k.

تُستخدم الإزاحات إلى اليسار غالبًا في مسائل المقابلات لإنشاء أقنعة البتات: إذ ينشئ 1 << k عددًا لا يكون فيه مفعّلًا سوى البت k. وهذا هو الأساس لجميع عمليات معالجة البتات — فتفعيل البتات وإلغاء تفعيلها وتبديلها والتحقق منها تبدأ جميعًا بـ 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

الإزاحة إلى اليمين: القسمة على قوى العدد اثنين

تنقل الإزاحة إلى اليمين (>>) جميع البتات إلى اليمين بمقدار k من المواضع، وتتجاهل بتات اليمين k. وهذا يكافئ القسمة الصحيحة على 2^k. وتكون الإزاحة إلى اليمين في Python حسابية دائمًا: إذ تُملأ البتات الموجودة في أقصى اليسار ببت الإشارة (0 للأعداد الموجبة و1 للأعداد السالبة).

من الحيل الشائعة في المقابلات: لاستخراج البت k من العدد n، استخدموا (n >> k) & 1. فهذا ينقل البت k إلى الموضع 0، ثم يعزل جميع البتات الأخرى بالقناع. وتُعد هذه الطريقة الأنظف للتحقق من أي بت محدد من دون الحاجة إلى حساب قناع كامل ومقارنته.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

مرجع سريع عملي لحيل البتات

فيما يلي مجموعة من أكثر صيغ معالجة البتات شيوعًا التي ستواجهونها في المقابلات. احفظوا هذه الأنماط، فهي تتكرر في عشرات المسائل:

n & 1 — التحقق مما إذا كان n فرديًا
n & (n-1) — إلغاء تفعيل أدنى بت مفعّل
n & -n — عزل أدنى بت مفعّل
n | (1 << k) — تفعيل البت k
n & ~(1 << k) — إلغاء تفعيل البت k
n ^ (1 << k) — تبديل البت k
(n >> k) & 1 — التحقق من البت k

# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

عدّ البتات المفعّلة (Popcount)

يُسمّى عدّ عدد البتات التي تساوي 1 في عدد صحيح عدّ البتات المفعّلة (popcount). وتتمثل الطريقة البدائية في المرور على جميع البتات. أما حيلة Brian Kernighan فهي أسرع، إذ تلغي تفعيل أدنى بت مفعّل بصورة متكررة باستخدام n &= n - 1، مع عدّ التكرارات حتى يصبح n مساويًا للصفر. وتزيل كل تكرار بتًا واحدًا يساوي 1 بالضبط، ولذلك تنفّذ الحلقة عددًا من المرات يساوي عدد البتات التي تساوي 1.

يوفّر Python 3.10 والإصدارات الأحدث الدالة int.bit_count() التي تعيد العدد مباشرة. أما في الإصدارات الأقدم، فتُعد حيلة Kernighan الطريقة اليدوية القياسية. وتحل هذه التقنية أيضًا مسألة 'Hamming Weight' على LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

معالجة البتات في Python: نقاط مهمة

على خلاف C/Java، تكون أعداد Python الصحيحة كبيرة بصورة اعتباطية — فلا يحدث تجاوز لسعة 32 بت أو 64 بت. وهذا يعني أنه يجب عليكم تطبيق قناع يدويًا على النتائج بعرض ثابت عند حل مسائل تتوقع سلوك 32 بت: استخدموا & 0xFFFFFFFF للإبقاء على أقل 32 بت فقط.

يعيد عامل NOT ~n في Python القيمة -(n+1)، وليس النسخة ذات البتات المعكوسة التي قد تتوقعونها في C. وفي مسائل 32 بت، استخدموا ~n & 0xFFFFFFFF أو احسبوا 0xFFFFFFFF ^ n للحصول على المتمّم المتوقع بعرض 32 بت. وتربك هذه الاختلافات كثيرًا من المرشحين المعتادين على معالجة البتات بأسلوب C.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

عوامل الإزاحة والضرب

توفر الإزاحتان إلى اليسار وإلى اليمين طريقة فائقة السرعة للضرب في قوى العدد اثنين أو القسمة عليها. وتكون إزاحات البتات على مستوى العتاد عمليات تُنفّذ بتعليمة واحدة، في حين يتطلب الضرب والقسمة عدة دورات. أما في Python، فضرب الأعداد الصحيحة فعّال أصلًا، لكن فهم هذه العلاقة يساعدكم على رؤية أنماط البتات بوضوح أكبر.

من الهويات المفيدة: للتحقق مما إذا كان n من مضاعفات 2^k، استخدموا (n & (2^k - 1)) == 0. يحتوي القناع 2^k - 1 على جميع البتات الدنيا k مفعّلة؛ ويعطي إجراء AND معه باقي القسمة على 2^k. وهذا يكافئ n % (2^k)، لكنه أسرع في اللغات المبنية على C.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

اختبار سريع

اختبروا فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.

مراجعة الدرس

تعلّمتم في هذا الدرس أن: AND يقنّع البتات، وOR يفعّل البتات، وXOR يبدّلها ويكتشف الاختلافات، وNOT يعكسها (ويعطي -(n+1) في Python)، والإزاحات تضرب وتقسم على قوى العدد اثنين، وأن n & (n-1) يلغي تفعيل أدنى بت مفعّل، ويشكّل أساس التحقق من قوى العدد اثنين وعدّ البتات، وأن Python لا يفرض تجاوزًا لسعة بعرض ثابت، ولذلك تتطلب مسائل 32 بت تطبيق قناع صريح باستخدام & 0xFFFFFFFF. ننتقل بعد ذلك إلى استكشاف خاصية المعكوس الذاتي لـ XOR لحل مجموعة مسائل الرقم الوحيد.

الأسئلة الشائعة

هل درس «العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات» مجاني؟

نعم — نص درس «العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.

ماذا ستتعلم في «العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات»؟

راجِع العوامل الستة على مستوى البت باستخدام جداول الحقيقة وأمثلة Python، وافهم علاقة الإزاحتين اليسرى واليمنى بالضرب والقسمة على اثنين. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟

لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.

كم من الوقت يستغرق درس «العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟

نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

العوامل على مستوى البت: AND وOR وXOR وNOT والإزاحات
الرقم الوحيد وخصائص XOR
أقنعة البتات: الضبط والمسح والتبديل والتحقق
عدّ البتات والرقم المفقود وعكس البتات

← العودة إلى Coding Interview Prep