Decimal to Binary
يُعطى لك عدد صحيح غير سالب n. أَعِد تمثيله الثنائي كسلسلة من 0 و1، من دون أصفار بادئة. العدد الوحيد الذي تبدأ إجابته بـ 0 هو الصفر نفسه، ويُكتب "0".
الدالة
- ninteger
- العدد المراد تحويله
- تُرجعstring
- الأرقام الثنائية للعدد n كسلسلة نصية
القيود
0 ≤ n ≤ 231-1- أنشئ السلسلة بنفسك بدلًا من استدعاء دالة مدمجة لتحويل الأساس.
أمثلة
- المدخلات
- n = 13
- المخرجات
- "1101"
- الشرح
13 = 8 + 4 + 1. خانات 8 و4 و2 و1 تحتوي على1و1و0و1، وهذا يُقرأ1101.
- المدخلات
- n = 0
- المخرجات
- "0"
- الشرح
- الصفر لا يحتوي على أي بِتّات مضبوطة، لكن الإجابة لا تزال بحاجة إلى رقم واحد، لذا فهي
"0"وليست سلسلة فارغة.
- المدخلات
- n = 64
- المخرجات
- "1000000"
- الشرح
64هو2^6، أي1واحد في خانة الـ64، يتبعه ستة أصفار في الخانات من 32 نزولًا إلى 1.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك تحويل n إلى أي أساس من 2 إلى 16 باستخدام الحلقة نفسها، مع استخدام الأحرف a إلى f للأرقام الأكبر من 9؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أيُّ رقمٍ ثنائيٍّ من
nيمكنك إيجاده دون معرفة أيٍّ من الأرقام الأخرى؟ فكّر في الأعداد الفردية والزوجية.الرقم الأخير هو
n % 2. قسمةnعلى 2 وإسقاط الباقي يزيل ذلك الرقم وينقل الرقم التالي إلى الخانة الأخيرة.كرّر: سجّل
n % 2، ثم اقسمnعلى 2، حتى تصبح قيمةnمساويةً لـ 0. تظهر الأرقام من الأقل إلى الأعلى، لذا اعكس ترتيبها في النهاية. للصفر إجابة خاصة به.
الحل
العدد الثنائي هو مجموع قوى العدد اثنين، ويُبيّن كل رقم ما إذا كانت إحدى هذه القوى موجودة في المجموع. يمكنك تحديد الأرقام بدءًا من الأعلى بطرح قوى العدد اثنين، أو قراءتها من الأسفل بوصفها بواقي القسمة المتكررة على 2. حلقة القسمة هي الطريقة القياسية: لا تحتاج أبدًا إلى إيجاد أكبر قوة أولًا، وتعمل بالطريقة نفسها مع كل أساس.
اطرح قوى العدد ٢ بدءًا من الأكبر
الفكرة
هكذا تحوّل يدويًا. أوجد أكبر قوة للعدد اثنين تتسع داخل n؛ فهي الرقم الأول، وهو 1. ثم انتقل إلى القوة الأقل في كل مرة. إذا كانت القوة لا تزال تتسع في القيمة المتبقية، فاكتب 1 واطرحها؛ وإلا فاكتب 0.
بالنسبة إلى 13، أكبر قوة هي 8. اكتب 1 ويتبقى 5. ثم تتسع 4 (اكتب 1، ويتبقى 1)، ولا تتسع 2 (اكتب 0)، وتتسع 1 (اكتب 1). تُقرأ الأرقام 1101. الرقم الأول دائمًا 1، لذلك لا يمكن أن يظهر صفر في البداية.
يتطلب إيجاد أكبر قوة بعض الحذر. تؤدي مضاعفة power حتى تتجاوز n إلى تجاوز سعة عدد صحيح ذي 32 بتًا عندما تكون n ≥ 2^30، لأن القوة التالية هي 2^31. إن مضاعفة power فقط ما دام power ≤ n / 2 تتوقف عند القوة المناسبة من دون تجاوز n مطلقًا. يستغرق عدد من 31 بتًا 31 خطوة، أي O(log n).
الخوارزمية
- إذا كان
nيساوي0، فأعِد"0". - ابدأ
powerبالقيمة 1، وضاعفها ما دامpower ≤ n / 2. - ما دام
power > 0: إذا كانn ≥ power، فألحِق1واطرحpowerمنn؛ وإلا فألحِق0. - اقسم
powerعلى 2 وكرّر. - أعِد الأرقام التي ألحقتها.
def toBinary(n):
if n == 0:
return "0"
# Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
power = 1
while power <= n // 2:
power *= 2
bits = []
while power > 0:
if n >= power:
bits.append("1")
n -= power
else:
bits.append("0")
power //= 2
return "".join(bits)القسمة المتكررة على 2
الفكرة
يحدد الرقم الثنائي الأخير من n ما إذا كان n فرديًا، وذلك باستخدام n % 2. يؤدي القسمة على 2 وإهمال الباقي إلى إزاحة كل رقم منزلة واحدة إلى اليمين، فيصبح الرقم التالي هو الأخير. كرر ذلك حتى لا يتبقى شيء، وستجمع كل الأرقام بدءًا من الأقل قيمة.
بالنسبة إلى 13: الباقي عند قسمة 13 هو 1، وعند قسمة 6 هو 0، وعند قسمة 3 هو 1، وعند قسمة 1 هو 1، ثم يصبح العدد 0. البواقي بالترتيب هي 1, 0, 1, 1؛ وعند عكس ترتيبها تصبح 1101. تتوقف الحلقة عندما يصل العدد إلى 0، لذا يكون الرقم الأعلى قيمة الذي تكتبه دائمًا 1، ولا يظهر أي صفر بادئ. العدد صفر نفسه لا يدخل الحلقة مطلقًا، ولهذا يحتاج إلى تحقق خاص به.
تُخفض كل خطوة العدد إلى النصف، لذا تحتاج قيمة من 31 بتًا إلى 31 خطوة، بزمن O(log n)، وتستهلك سلسلة الأرقام مساحة O(log n).
الخوارزمية
- إذا كان
nيساوي0، فأعِد"0". - طالما أن
n > 0، أضِفn % 2كرقم، واجعل قيمةnتساويn / 2بعد التقريب إلى الأسفل. - اعكس ترتيب الأرقام، لأنها ظهرت من الأصغر أهميةً أولًا.
- أعِدها كسلسلة نصية.
def toBinary(n):
if n == 0:
return "0"
bits = []
while n > 0:
# The remainder is the lowest bit that is left.
bits.append(str(n % 2))
n //= 2
# The bits came out lowest first, so turn them around.
bits.reverse()
return "".join(bits)
أخطاء شائعة وحالات حدّية
الحلقة قصيرة، ومعظم الإجابات الخاطئة تنتج عن خطأي طرفيها.
- إرجاع سلسلة فارغة عند
0. لا تعمل حلقة القسمة عندما يكون العدد صفرًا، لذا تحقّق من ذلك أولًا. - نسيان عكس الترتيب. تظهر البواقي بدءًا من الرقم الأقل قيمة، لذا ينتج
6على هيئة011بدلًا من110. - استخدام
/في لغة تُرجع فيها هذه العملية كسرًا، مثل JavaScript أو Lua أو PHP. يجب أن تصبح13 / 2مساويةً لـ6، لذا قرّب إلى الأسفل أو استخدم القسمة الصحيحة. - بناء أكبر قوة بالمضاعفة إلى أن تتجاوز
n. عندما تكونn = 2^31-1، لا تتسع قيمة القوة التالية،2^31، في عدد صحيح من 32 بت. - حجز مساحة غير كافية في C. يحتاج عدد من 31 بت إلى 31 محرفًا، بالإضافة إلى
'\0'الختامي.
أسئلة شائعة4
كيف تحوّل عددًا عشريًا إلى ثنائي؟
اقسم العدد على 2 مرارًا وتكرارًا، وسجّل باقي القسمة في كل مرة، حتى يصبح العدد 0. اقرأ البواقي من الأخير إلى الأول. بالنسبة إلى 13، تكون البواقي 1، 0، 1، 1، لذا فإن 13 بالنظام الثنائي هو 1101.
لماذا تُقرأ البواقي بترتيب عكسي؟
يخبرك القسمة الأولى على 2 ما إذا كان العدد فرديًا، وهي الرقم الثنائي الأخير. وتكشف كل قسمة لاحقة عن الرقم التالي إلى اليسار. لذا تظهر البواقي بدءًا من الرقم الأقل قيمة، وتعكس ترتيبها لكتابة العدد بالطريقة المعتادة.
ما هو التعقيد الزمني لتحويل العدد العشري إلى ثنائي؟
تُقسِّم كل خطوة العدد إلى النصف، لذا تتكرر الحلقة مرة واحدة لكل رقم ثنائي، أي نحو log2(n) مرة. وهذا يستغرق زمنًا قدره O(log n)، كما أن سلسلة الإجابة تشغل مساحة قدرها O(log n). وبالنسبة إلى عدد صحيح من 32 بت، فهذا يعني 31 خطوة كحد أقصى.
هل يمكنك التحويل إلى النظام الثنائي باستخدام عمليات البت بدلًا من القسمة؟
نعم. يعطي n & 1 البت الأقل، ويحذفه n >> 1، وهذا يعادل n % 2 وn / 2 للأعداد غير السالبة. تظل الحلقة وعملية العكس كما هما. القسمة أسهل في الشرح، بينما تُستخدم نسخة الإزاحة كثيرًا في البرمجة منخفضة المستوى.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def toBinary(n):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 13
المتوقع
"1101"