Competitive Programming Academy · درس

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

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

الدرس 3 من 413 خطوة

عدّ البتات وأدنى بت معيّن درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 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). إنها تعبيرات قوية في سطر واحد. 🎉

البدء مجانًا

تعلم Python مع معلم ذكاء اصطناعي — مجانًا

اكتب وقم بتشغيل أكوادك الفعلية في المتصفح، واحصل على مساعدة فورية من معلم ذكاء اصطناعي متاح 24/7، واستمر من حيث توقفت على الويب أو في التطبيق.

الدورات: 30
الدروس: 120

ابدأ التعلم مجانًا عرض الدورة الكاملة

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

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

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

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

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

هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟

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

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

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

هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟

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

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

← العودة إلى Competitive Programming Academy