Number of 1 Bits
يُعطى لك عدد صحيح غير سالب n. اكتب n بالنظام الثنائي، وأعِد عدد أرقامه التي تساوي 1. يُسمّى هذا العدد أيضًا عدد البتات المضبوطة، أو عدد البتات ذات القيمة 1، أو وزن هامينغ. على سبيل المثال، العدد 6 هو 110 بالنظام الثنائي، لذا يحتوي على بتّين قيمتهما 1.
الدالة
- ninteger
- عدد صحيح غير سالب يمكن تمثيله في عدد صحيح موقّع من 32 بت
- تُرجعinteger
- عدد خانات 1 في التمثيل الثنائي للعدد n
القيود
0 ≤ n ≤ 231-1
أمثلة
- المدخلات
- n = 11
- المخرجات
- 3
- الشرح
- العدد 11 هو
1011بالنظام الثنائي، أي 8 + 2 + 1. ثلاثة من أرقامه الثنائية الأربعة تساوي 1، لذا فالإجابة هي 3.
- المدخلات
- n = 128
- المخرجات
- 1
- الشرح
- 128 هو 2^7، ويُكتب
10000000: واحد يتبعه أصفار، لذا الإجابة هي 1.
- المدخلات
- n = 2147483645
- المخرجات
- 30
- الشرح
- 2^31-1 = 2147483647 يتكون من واحد وثلاثين بتًا قيمتها 1 متتالية. 2147483645 هو ذلك العدد ناقص 2، ما يطفئ البت الذي قيمته 2 ويُبقي 30 واحدًا.
سؤال إضافي
إذا نُفِّذت هذه الدالة ملايين المرات، فكيف يمكنك عدّ بتات عدد ذي 32 بتًا باستخدام أربع عمليات بحث في جدول يحتوي على 256 عددًا محسوبًا مسبقًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
انظر فقط إلى الرقم الثنائي الأخير من
n. كيف يمكنك قراءته دون تحويلnإلى سلسلة نصية، وكيف تنقل بعد ذلك الرقم التالي إلى الخانة الأخيرة؟n & 1(أوn % 2) هو البِت الأخير، والإزاحة إلى اليمين بمقدار واحد (أو القسمة على 2 مع التقريب إلى الأسفل) تزيله. اجمع البِتات الأخيرة حتى تصبح قيمةnتساوي 0.للحصول على حلقة أقصر، استخدم
n & (n-1): تكونnبعد إطفاء أقل بت يساوي 1 فيها. احسب عدد المرات التي يمكنك فيها تطبيق ذلك قبل أن تصلnإلى 0. عندها تعمل الحلقة مرة واحدة لكل بت يساوي 1 بدلًا من مرة واحدة لكل رقم ثنائي.
الحل
افحص الأرقام الثنائية لـ n دون إنشاء سلسلة نصية. تتطلب قراءة البت الأخير وإزاحته خطوة واحدة لكل رقم ثنائي، بحد أقصى 31. ويتطلب مسح أقل بت يساوي 1 باستخدام n & (n-1) خطوة واحدة لكل بت يساوي 1، أي بعدد يساوي الإجابة تمامًا.
تحقّق من الجزء الأخير وأزِحه إلى اليمين
الفكرة
n & 1 هو الرقم الثنائي الأخير من n: يكون 1 عندما يكون n فرديًا، و0 عندما يكون زوجيًا. أضِفه إلى العَدّ. بعد ذلك، يحذف n >> 1 ذلك الرقم وينقل الرقم التالي إلى الموضع الأخير؛ وبالنسبة إلى عدد غير سالب، فهذا يعني القسمة على 2 مع التقريب إلى الأسفل. بالنسبة إلى 11، أي 1011، تكون البتات الأخيرة 1 ثم 1 ثم 0 ثم 1 مع تناقص n حتى يصل إلى 0: ثلاث بتات قيمتها 1.
تتوقف الحلقة عندما تصبح n مساويةً لـ0، لذا لا تمرّ على الأصفار البادئة: نحو log2(n) خطوة، و8 خطوات للعدد 128، وبحد أقصى 31 خطوة. ولا تخزّن سوى n والعَدّ.
الخوارزمية
- ابدأ عدّادًا عند 0.
- طالما أن
nأكبر من 0، أضفn & 1إلى العدّاد. - أزِح
nإلى اليمين بمقدار بت واحد. - عندما تصل
nإلى 0، أعد العدّاد.
def hammingWeight(n):
count = 0
while n > 0:
count += n & 1 # the last bit is 1 or 0
n >>= 1 # drop the last bit
return countامسح أقل بتّ مُفعّل باستخدام n & (n-1)
الفكرة
يحوّل طرح 1 أقلّ بت قيمته 1 إلى 0، وكل بت قيمته 0 تحته إلى 1، ويُبقي البتات التي فوقه دون تغيير. لذا فإن n & (n-1) يحتفظ بالبتات العليا ويمحو أقلّ بت قيمته 1: العدد 12 هو 1100، والعدد 11 هو 1011، و1100 & 1011 هو 1000.
تزيل كل خطوة بتًا واحدًا قيمته 1 بالضبط، لذا فإن عدد الخطوات حتى يصبح n مساويًا لـ 0 هو الإجابة. يحتاج العدد 128 إلى خطوة واحدة بدلًا من 8، مع أن العدد 2^31-1 لا يزال يحتاج إلى 31 خطوة. لا يدعم Lua 5.1 معاملات البت، لذا فإن نسخته تجد أقلّ بت قيمته 1 عن طريق القسمة على 2 ثم تطرحه؛ وتظل الحلقة تعمل مرة واحدة لكل بت قيمته 1.
الخوارزمية
- ابدأ العدّاد عند 0.
- ما دام
nلا يساوي 0، استبدلnبـn & (n-1). - أضف 1 إلى العدّاد بعد كل استبدال.
- أعِد العدّاد.
def hammingWeight(n):
count = 0
while n != 0:
n &= n - 1 # turn off the lowest 1 bit
count += 1
return count
أخطاء شائعة وحالات حدّية
- التكرار ما دام
n > 1. تتوقف الحلقة قبل البت الأخير ذي القيمة 1، وتُرجع 0 عندما تكونn = 1. - القسمة باستخدام عدد عشري. في JavaScript وLua وR، تكون
11 / 2مساوية لـ 5.5، وتكون البواقي الناتجة كسورًا. قرّب إلى الأسفل باستخدامMath.floorأوmath.floorأو%/%، أو استخدم الإزاحة بدلًا من ذلك. - كتابة
n & 1في Lua 5.1. لا تدعم هذه اللغة معاملات البت، لذا لن يُترجم الكود؛ استخدمn % 2وmath.floor(n / 2).
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة عدد البتات 1؟
تعمل حلقة الإزاحة مرة واحدة لكل رقم ثنائي: O(log n)، وبحد أقصى 31 خطوة هنا. تعمل حلقة n & (n-1) مرة واحدة لكل بت يساوي 1: O(k)، حيث k هي الإجابة. وتستخدم كلتاهما مساحة إضافية O(1).
هل توجد دالة مضمّنة تحسب عدد البِتّات المضبوطة؟
تتضمن معظم اللغات دالةً كهذه، وغالبًا ما تكون مدعومة بتعليمة واحدة من المعالج: Integer.bitCount في Java، و__builtin_popcount في GCC، وbits.OnesCount في Go، وcount_ones في Rust، وint.bit_count في Python 3.10 والإصدارات الأحدث. في مقابلة، اكتب الحلقة واذكر الدالة المضمنة.
ما الفرق بين وزن هامنج ومسافة هامنج؟
وزن هامِنغ للعدد هو عدد خاناته الثنائية التي تساوي 1، وهذا ما تُرجعه هذه المسألة. مسافة هامِنغ بين عددين هي عدد مواضع البتات التي يختلفان فيها: احسب عدد البتات التي تساوي 1 في a ^ b، إذ إن XOR يضبط بالضبط المواضع التي يختلفان فيها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def hammingWeight(n):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
n = 11
الإخراج المتوقع
3