Binary to Decimal
تحصل على سلسلة نصية s تمثّل عددًا غير سالب بالنظام الثنائي، باستخدام المحرفين 0 و1 فقط. أعد قيمة ذلك العدد كعدد صحيح عادي. لا تحتوي السلسلة على أصفار بادئة، باستثناء العدد صفر، الذي يتكوّن من المحرف 0 وحده.
الدالة
- sstring
- الأرقام الثنائية للعدد
- تُرجعinteger
- قيمة s كعدد صحيح
القيود
1 ≤ s.length ≤ 31sلا يحتوي إلا على0و1.sيبدأ بـ1، ما لم تكن قيمةsهي"0".- اقرأ الأرقام بنفسك بدلًا من استدعاء تحويل أساس مدمج.
أمثلة
- المدخلات
- s = "1101"
- المخرجات
- 13
- الشرح
- بالقراءة من اليمين، تكون قيم الخانات 1 و2 و4 و8. يحتوي
1101على 1 في خانات 8 و4 و1، و8 + 4 + 1 = 13.
- المدخلات
- s = "0"
- المخرجات
- 0
- الشرح
- لا يحتوي
0على أي 1 في أي منزلة، لذا فقيمته هي0.
- المدخلات
- s = "10000000"
- المخرجات
- 128
- الشرح
- الرقم 1 الوحيد يقع إلى يمينه سبعة أصفار، لذا فهو في المنزلة التي قيمتها
2^7 = 128.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك قراءة عدد مكتوب بأي أساس من 2 إلى 16 باستخدام الحلقة نفسها، حيث تمثل الأحرف a إلى f الأرقام من 10 إلى 15؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
في النظام العشري، قيمة أرقام
347هي 300 و40 و7. ما قيمة كل رقم ثنائي؟تساوي قيمة الرقم الثنائي الأيمن 1، وتتضاعف قيمة المنزلة مع كل خطوة إلى اليسار: 1، 2، 4، 8 وهكذا. والعدد هو مجموع قيم المنازل التي تحتوي على 1.
يمكنك تجنّب حساب القوى: ابدأ من اليسار، ومع كل رقم اجعل القيمة المتراكمة تساوي ضعف نفسها مضافًا إليها ذلك الرقم. بعد الرقم الأخير، تكون القيمة المتراكمة هي الإجابة.
الحل
يمثل كل رقم ثنائي قوةً للعدد 2، ويُحدَّد ذلك بحسب بُعده عن الطرف الأيمن. يمكنك جمع تلك القوى بدءًا من اليمين، أو قراءة السلسلة النصية من اليسار ومضاعفة القيمة في كل خطوة. حلقة التضعيف لا تحسب قوةً أبدًا، وهي الحلقة نفسها التي تستخدمها لقراءة النص العشري، مع استخدام 2 بدلًا من 10.
أضف القيم المكانية بدءًا من اليمين
الفكرة
تساوي قيمة الرقم الموجود في أقصى اليمين 1، والرقم الذي يليه 2، ثم 4 و8 وهكذا، إذ تتضاعف القيمة مع كل خطوة إلى اليسار. العدد هو مجموع القيم المكانية التي تحتوي على 1. لذا انتقل من الحرف الأخير إلى الأول، واحتفظ بالقيمة المكانية الحالية في power، وأضفها كلما كان الرقم 1.
في 1101، تصادف 1 (أضف 1)، و0 (تجاوز 2)، و1 (أضف 4)، و1 (أضف 8)، فيكون المجموع 13. تتم زيارة كل رقم مرة واحدة، لذا تستغرق الحلقة وقتًا قدره O(n) وتستخدم ذاكرة بحجم عددين.
انتبه إلى حجم power. في سلسلة من 31 رقمًا، تصل قيمته إلى 2^30 عند الرقم الأخير، ثم تتضاعف مرة أخرى لتصبح 2^31، وهذا لا يتسع له عدد صحيح موقّع من 32 بت. احتفظ بـ power في متغير من 64 بت، أو توقّف عن مضاعفته بعد الرقم الأخير.
الخوارزمية
- عيّن
total = 0وpower = 1. - امشِ عبر السلسلة من آخر حرف فيها إلى أول حرف.
- إذا كان الحرف هو
1، فأضفpowerإلىtotal. - ضاعف
powerقبل الانتقال خانة واحدة إلى اليسار. - أعِد
total.
def toDecimal(s):
total = 0
power = 1 # the place value of the rightmost digit
for i in range(len(s) - 1, -1, -1):
if s[i] == "1":
total += power
power *= 2
return totalضاعِف واجمع من اليسار
الفكرة
اقرأ السلسلة من اليسار واحتفظ بـ value، وهو العدد الذي تمثّله الأرقام المقروءة حتى الآن. إن إضافة رقم ثنائي آخر تُزيح كل رقم سابق منزلةً واحدة إلى اليسار، ما يضاعف قيمته، ثم تضيف الرقم الجديد. لذا تكون كل خطوة هي value = value * 2 + digit.
بالنسبة إلى 1101، تصبح قيمة value هي 1، ثم 1 * 2 + 1 = 3، ثم 3 * 2 + 0 = 6، ثم 6 * 2 + 1 = 13. كل بادئة من السلسلة هي عدد ثنائي أصغر، وتحفظ الحلقة هذا العدد بالضبط، لذا تكون القيمة الكاملة محفوظة فيها بعد الرقم الأخير.
لا تتجاوز القيمة أبدًا الإجابة النهائية، لذا تبقى ضمن 2^31-1 لسلسلة من 31 رقمًا، ويكفي عدد صحيح من 32 بتًا. الرقم هو رمز الحرف مطروحًا منه رمز '0'، ما يحوّل '1' إلى 1 و'0' إلى 0. هذه هي الطريقة القياسية لتحليل عدد من نص بأي أساس.
الخوارزمية
- اجعل
value = 0. - لكل حرف من اليسار إلى اليمين، حوّله إلى رقم بطرح رمز
'0'. - اجعل
value = value * 2 + digit. - أعِد
value.
def toDecimal(s):
value = 0
for ch in s:
# Shift the digits read so far one place left, then add the new one.
value = value * 2 + (ord(ch) - ord("0"))
return value
أخطاء شائعة وحالات حدّية
تنتج معظم الإجابات الخاطئة عن اتجاه المرور أو عن نوع الرقم.
- إعطاء الرقم الموجود في أقصى اليسار قيمةَ منزلة تساوي 1. تبدأ قيم المنازل من الطرف الأيمن، لذا مرّ من الحرف الأخير، أو استخدم حلقة المضاعفة بدءًا من اليسار.
- إضافة الحرف بدلًا من الرقم. في العديد من اللغات،
'1'هو العدد 49، لذا فإنvalue * 2 + '1'أكبر بكثير مما ينبغي. اطرح'0'أولًا. - تجاوز قيمة المنزلة للحد المسموح. تؤدي مضاعفة
powerبعد الرقم الحادي والثلاثين إلى القيمة2^31، التي تلتف أو تتسبب في انهيار البرنامج عند استخدام عدد صحيح من 32 بت. - حساب كل قيمة منزلة باستخدام دالة قوة للأعداد ذات الفاصلة العائمة. في C وC++ وJava، تُرجع
pow(2, k)قيمة من النوعdouble، ويجب تحويل الناتج إلى عدد صحيح.
أسئلة شائعة4
كيف تحوّل من النظام الثنائي إلى النظام العشري؟
امنح كل رقم قيمة منزلية: 1 للرقم الموجود أقصى اليمين، ثم 2 و4 و8 وهكذا باتجاه اليسار. اجمع القيم المنزلية للأرقام التي تساوي 1. بالنسبة إلى 1101، يكون الناتج 8 + 4 + 1 = 13.
لماذا تنجح مضاعفة القيمة؟
إن كتابة رقم إضافي في نهاية عدد ثنائي تُحرّك كل رقم سابق خانة واحدة إلى اليسار، وتكون قيمة كل خانة ضعف قيمة الخانة التي على يمينها. لذا تتضاعف القيمة القديمة، ويضيف الرقم الجديد 0 أو 1. ويؤدي تكرار ذلك من الرقم الأول إلى الأخير إلى تكوين العدد كاملًا.
ما هو التعقيد الزمني لتحويل عدد ثنائي إلى عدد عشري؟
تمرّ كلتا الحلقتين على كل واحد من الأحرف n مرة واحدة، لذا يستغرق تنفيذهما وقتًا قدره O(n). ولا تحتفظان إلا برقم واحد أو رقمين، ما يعني استخدام مساحة إضافية قدرها O(1). بالنسبة إلى سلسلة مكوّنة من 31 حرفًا، فهذا يعني 31 خطوة.
هل يمكنك تحويل النظام الثنائي إلى النظام العشري باستخدام إزاحات البِتات؟
نعم. تعمل value << 1 على مضاعفة القيمة، وتضبط | digit البت الأقل أهمية، لذا فإن value = (value << 1) | digit تؤدي الوظيفة نفسها التي تؤديها value * 2 + digit. توضح صيغة الإزاحة أنك تحرّك البتات، بينما تعمل الصيغة الحسابية أيضًا مع قواعد غير 2.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def toDecimal(s):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "1101"
المتوقع
13