Power of Two
لديك عدد صحيح n. أعد true إذا كان n قوةً للعدد اثنين، أي n = 2^k لعدد صحيح غير سالب k ≥ 0، وأعد false خلاف ذلك. لذا تُعدّ 1 و2 و4 و8 ضمن ذلك، بينما لا يُعدّ 0 أو 6 أو أي عدد سالب.
الدالة
- ninteger
- العدد الصحيح المراد اختباره، والذي قد يكون صفرًا أو سالبًا
- تُرجعboolean
- صحيح إذا كان n يساوي 2^k لبعض k ≥ 0، وخطأ خلاف ذلك
القيود
-231 ≤ n ≤ 231-1
أمثلة
- المدخلات
- n = 16
- المخرجات
- true
- الشرح
- 16 = 2 × 2 × 2 × 2 = 2^4. بالنظام الثنائي، هو
10000، أي بت واحد قيمته 1.
- المدخلات
- n = 24
- المخرجات
- false
- الشرح
- 24 = 8 × 3. بالتنصيف نحصل على 12 و6 ثم 3، وهو عدد فردي لكنه ليس 1. في النظام الثنائي، 24 هو
11000، وفيه بتّان قيمتهما 1.
- المدخلات
- n = 1
- المخرجات
- true
- الشرح
- 1 = 2^0، لذا فهو قوة للعدد 2. تمثيله الثنائي
1يحتوي على بت واحد فقط قيمته 1.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
باستخدام حيل البتات نفسها، هل يمكنك اختبار ما إذا كان n قوةً للعدد أربعة دون استخدام حلقة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اكتب بعض قوى العدد اثنين بالنظام الثنائي:
1،10،100،1000. ما القاسم المشترك بينها الذي لا ينطبق على العدد 6 (110)؟قوة العدد 2 تحتوي على بت 1 واحد بالضبط. قارن
nمعn-1بالنظام الثنائي: طرح 1 يقلب أدنى بت 1 إلى 0 وكل بت 0 أدناه إلى 1.إذًا تكون
nقوةً للعدد 2 بالضبط عندما تكون موجبة ويكون ناتج إجراء AND بينها وبينn-1هو 0. اختبر الإشارة قبل البِتّات، لأن 0 والأعداد السالبة ليست أبدًا قوى للعدد 2.
الحل
للعدد الذي هو قوة للعدد 2 شكل ثابت في النظام الثنائي: بت واحد قيمته 1 يتبعه أصفار، مثل 10000 للعدد 16. يمكنك التحقق من هذا الشكل بقسمة n على 2 حتى يصبح فرديًا، وهذا يستغرق ما يصل إلى 31 خطوة. أو يمكنك التحقق منه في خطوة واحدة باستخدام n & (n-1)، الذي يمسح أقل بت قيمته 1 ويترك 0 فقط عندما يكون ذلك البت هو الوحيد. في كلتا الطريقتين، يأتي التحقق من الإشارة أولًا، لأن الأعداد صفر والسالبة تُفسد الشيفرة الواضحة.
اقسم على 2 ما دام العدد زوجيًا
الفكرة
إذا كان n = 2^k، فيمكنك قسمته على 2 تمامًا k مرات والوصول إلى 1، وتكون كل قيمة على طول الطريق زوجية. إذا كان لدى n عامل فردي أكبر من 1، فستتوقف عملية القسمة على 2 عند عدد فردي ليس 1. بالنسبة إلى 16: 16، 8، 4، 2، 1، لذا فالإجابة صحيحة. وبالنسبة إلى 24: 24، 12، 6، 3، والعدد 3 فردي لكنه ليس 1، لذا فالإجابة خاطئة.
أعِد false للقيمة n ≤ 0 قبل الحلقة. فلا توجد قوة للعدد 2 تساوي صفرًا أو تكون سالبة، ولن تنتهي الحلقة عند 0، لأن 0 عدد زوجي ونصف 0 يساوي 0 أيضًا.
في كل خطوة، تُقسم n على 2، لذا يستغرق إدخال ذو 32 بت 31 خطوة على الأكثر: زمن O(log n) ومساحة O(1).
الخوارزمية
- إذا كان
n ≤ 0، فأعِد false. - طالما أن
nزوجي، اقسمه على 2. - أعِد ما إذا كان
nيساوي 1 الآن.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1امسح أقل بتّ مفعّل باستخدام n & (n-1)
الفكرة
اكتب قوةً للعدد 2 بالنظام الثنائي، وستكون عبارة عن 1 واحدة يتبعها أصفار: 16 هي 10000. طرح 1 يحوّل تلك الـ1 إلى 0 وكل 0 تحتها إلى 1: 15 هي 01111. لا يشترك العددان في أي بت قيمته 1، لذا فإن 16 & 15 تساوي 0.
أي عدد موجب آخر يحتوي على الأقل على بتّين قيمتهما 1. يغيّر طرح 1 أدنى بت قيمته 1 والأصفار التي تحته فقط، لذا يظهر كل بت أعلى قيمته 1 في كلا العددين، ولا تكون نتيجة عملية AND مساويةً لـ0. بالنسبة إلى 24، وهو 11000، تحصل على 23 = 10111، وتكون 24 & 23 هي 10000، أي 16.
تحقّق أولًا من n > 0. إن 0 & -1 تساوي 0، وفي الحساب ذي 32 بتًا، يكون -2^31 بتًا واحدًا قيمته 1 تتبعه 31 صفرًا، لذا فإن عملية AND وحدها ستعدّ كليهما قوتين للعدد 2. يتكوّن الاختبار الكامل من مقارنة واحدة وطرح واحد وعملية AND واحدة: زمن ومساحة O(1). لا تتضمن Lua 5.1 عامل AND، لذا ينشئ كود Lua نتيجة AND بتًا واحدًا في كل مرة، في ما يصل إلى 31 خطوة لقيمة n ذات 32 بتًا؛ والاختبار هو نفسه.
الخوارزمية
- إذا كان
n ≤ 0، فأعِد false. - احسب
n & (n-1)، وهيnبعد مسح أقل بت يساوي 1 فيها. - أعِد ما إذا كانت تلك النتيجة تساوي 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
أخطاء شائعة وحالات حدّية
اختبار البتات يتكوّن من سطر واحد، ومعظم الأخطاء تتعلق بالمدخلات التي لم يُصمَّم للتعامل معها.
- تجاوز فحص الإشارة.
0 & (0-1)يساوي 0، لذا يجتاز 0 اختبار AND. ومع الأعداد الصحيحة ذات 32 بتًا، يجتاز-2^31الاختبار أيضًا، لأن تمثيله الثنائي يتضمن بتًا واحدًا قيمته 1. يجب أن تُعيد الحالتان القيمة false. - تشغيل حلقة التنصيف على 0. الصفر عدد زوجي، وتنصيفه يعطي 0 مرة أخرى، لذا لا تنتهي الحلقة أبدًا.
- إغفال الأقواس. للأسبقية
==على&، لذا في C وC++ وJavaScript تُقرأn & n - 1 == 0على أنهاn & ((n - 1) == 0)وتعطي إجابة خاطئة من دون أي خطأ؛ أما Java وC# فترفضانها بسبب خطأ في النوع. اكتب(n & (n - 1)) == 0. - استخدام اللوغاريتمات. في الدقة المضاعفة، تكون نتيجة
log(536870912) / log(2)هي 29.000000000000004 بدلًا من 29، لذا فإن التحقق من كون الناتج عددًا صحيحًا يجعل2^29يعطي القيمة false.
أسئلة شائعة4
كيف تتحقق مما إذا كان عددٌ ما قوةً للعدد اثنين؟
أعِد true عندما تكون n > 0 وn & (n-1) تساوي 0. للعدد الذي هو قوة للعدد 2 بتّ 1 واحد بالضبط، وطرح 1 منه يمحو هذا البت ويضبط البتات التي تسبقه فقط، لذا تكون نتيجة AND هي 0. من دون عمليات البتات، اقسم n على 2 ما دام زوجيًا، وتحقق من أن الناتج النهائي هو 1.
لماذا تؤدي العملية n & (n-1) إلى مسح أقل بتّ مُفعّل؟
يستعير طرح 1 من أدنى بت قيمته 1: يصبح ذلك البت 0، وتصبح كل بتات 0 الواقعة تحته 1، بينما تبقى البتات الأعلى كما هي. ويُبقي إجراء AND مع القيمة الأصلية على البتات المضبوطة في كلتيهما فقط، وهي بالضبط البتات الأعلى. وفي حالة قوة للعدد 2، لا توجد بتات أعلى، لذا تكون النتيجة 0.
ما هو التعقيد الزمني لمسألة قوة العدد 2؟
يعمل فحص n & (n-1) بزمن ومساحة O(1): مقارنة واحدة، وطرح واحد، وعملية AND واحدة. تعمل حلقة التنصيف بزمن O(log n)، وبحد أقصى 31 خطوة لعدد صحيح من 32 بت.
هل 1 قوة للعدد 2؟ وهل 0 كذلك؟
العدد 1 هو قوة للعدد 2، لأن 2^0 = 1، وصيغته الثنائية تحتوي على بت واحد قيمته 1. أما 0 فليس كذلك: لا يوجد أس صحيح يعطي 0، ولا يحتوي على أي بت قيمته 1. والأعداد السالبة ليست قوى للعدد 2 أبدًا أيضًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isPowerOfTwo(n):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 16
المتوقع
true