Coding Interview Prep · درس

عدّ البتات وأدنى بت معيّن

استخدام popcount وحيلة n & -n

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

عدّ البتات المعيّنة

تسأل مسائل كثيرة عن عدد البتات المعيّنة في عدد ما، ويُسمى ذلك popcount. ويظهر هذا المفهوم في أحجام المجموعات الجزئية، وفحوصات التكافؤ، وحساب النقاط. 🔢

دالة العد المضمّنة في Python

أسرع طريقة لعد البتات المعيّنة هي استخدام طريقة العدد الصحيح bit_count(). بلا حلقات أو تعقيد، ستحصل مباشرة على عدد الواحدات.

print((13).bit_count())  # 0b1101 has 3 ones

العد باستخدام bin و count

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

print(bin(13).count('1'))  # 3

أدنى بت معيّن

أدنى بت معيّن هو أقصى 1 إلى اليمين في العدد. وعزله خطوة أساسية في أشجار Fenwick وحيل المجموعات الجزئية التي ستتعلمها لاحقًا.

عزل البت باستخدام n و -n

تحافظ الحيلة الشهيرة n & -n على أدنى بت معيّن فقط. وتجعل الأعداد السالبة بتمثيل المتمم الثنائي هذه الحيلة تعمل بطريقة مذهلة.

n = 12  # 0b1100
print(n & -n)  # 4 = 0b100

سبب نجاح n و -n

يؤدي نفي العدد إلى قلب جميع البتات ثم إضافة 1، لذلك تنقلب كل البتات الواقعة أسفل أدنى 1. وتُبقي عملية AND ذلك البت الواحد فقط.

إزالة أدنى بت معيّن

يستعير طرح 1 عبر الأصفار المتتالية، لذلك يمسح التعبير n & (n - 1) أدنى بت معيّن. كرّر العملية لإزالة الواحدات واحدًا تلو الآخر.

n = 12  # 0b1100
print(n & (n - 1))  # 8 = 0b1000

عدّ Brian Kernighan

كرّر الحلقة ما دام العدد غير صفري، وامسح أدنى بت في كل مرة. تعمل الحلقة مرة واحدة لكل بت معيّن، لذا فهي سريعة عند إجراء popcount لعدد قليل من البتات المعيّنة.

c = 0
while n:
    n &= n - 1
    c += 1

التحقق من كون العدد قوة للعدد 2

تحتوي قوة موجبة للعدد 2 على بت معيّن واحد بالضبط، لذلك يساوي n & (n - 1) القيمة 0. وتكفي عملية AND واحدة لمعرفة ذلك فورًا.

def is_pow2(n):
    return n > 0 and (n & (n - 1)) == 0

التكافؤ من خلال عدد البتات

إن تكافؤ عدد ما هو ببساطة باقي قسمة popcount الخاص به على 2. وهذا يجيب عن أسئلة كون عدد الواحدات فرديًا أو زوجيًا في خطوة واحدة.

parity = (13).bit_count() & 1  # 1

اختيار الأداة الأسرع

للحصول على السرعة القصوى استخدم bit_count؛ وللمرور على البتات المعيّنة استخدم حلقة n & (n-1). يساعد اختيار الأداة المناسبة على اجتياز حدود الوقت الصارمة. ⚡

تحقق سريع

اختبر حيلة عزل أدنى بت معيّن.

مراجعة: عدّ البتات

يمكنك عدّ الواحدات باستخدام bit_count، وعزل أدنى بت باستخدام n & -n، وإزالته باستخدام n & (n-1). إنها تعبيرات قوية في سطر واحد. 🎉

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

هل درس «عدّ البتات وأدنى بت معيّن» مجاني؟

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

ماذا ستتعلم في «عدّ البتات وأدنى بت معيّن»؟

استخدام popcount وحيلة n & -n تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

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

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

كم من الوقت يستغرق درس «عدّ البتات وأدنى بت معيّن»؟

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

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

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

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

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