لوغاريتم صحيح ذو أساس 2 في O (1)

غالبًا ما يكون من الضروري حساب الجزء الكامل من لوغاريتم الأساس 2 لأي عدد صحيح.



القرار المباشر هو عمل حلقة وفي هذه الحلقة قسّم الرقم باستمرار على اثنين حتى يصبح صفرًا. كم عدد هذه الانقسامات حدثت ، هذه هي قيمة اللوغاريتم. نعم ، هذه الطريقة تعمل ولها الحق في الحياة ، لكني أريد أن أوضح كيف يمكن القيام بها دون أي دورات وهياكل معقدة.



لذلك ، نريد حساب الصيغة التالية:

$$

$$y = [log_2(x)], x - ,$$

القرار

بالنسبة لأولئك الذين لا يهتمون بالتفكير ، سأقدم على الفور وظائف جاهزة لحساب اللوغاريتم:

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

تفسيرات

أولًا ، دعنا نحول الرقم س إلى رمز ثنائي بطول معين.



على سبيل المثال ، الطول = 8 ، لكن هذا لا يهم ويمكن أن يكون طول الرقم أيًا.



تذكر الآن ما تقوم عليه ترجمة الرقم إلى الترميز الثنائي. لتمثيل الرقم كمجموع قوى لاثنين. سيحدد رقم الدرجة موضع البت ، وهو 1. على سبيل المثال:$$$45 = 32 + 8 + 4 + 1 = 2^5 + 2^3 + 2^2 + 2^0$... أولئك. أرقام الدرجات 5 و 3 و 2 و 0. هذا يعني أن البتات الخامسة والثالثة والثانية والصفر تساوي 1. باقي البتات بينهما تساوي صفرًا. تبدأ القطع من الجانب الأيمن. اتضح أن$$$45_{10} = 101101_2$



يمكن ملاحظة أن الترجمة إلى الترميز الثنائي ترتبط ارتباطًا وثيقًا بالأُس ، واللوغاريتم هو معكوس الأس ويساوي الأس.

$$

$$2^y = x, y = log_2(x)$$

علاوة على ذلك ، فإن الأس الذي تحتاج إلى رفعه 2 هو عدد بت واحد في تدوين ثنائي. اتضح أنه إذا وجدنا عدد بت واحد ، فسنحصل على الجزء الصحيح من قيمة اللوغاريتم للأساس اثنين. على سبيل المثال ، إذا كان 32 = 100000 ، فإن البتة الواحدة في الخانة الخامسة ، وبالتالي فإن اللوغاريتم هو 5.



ولكن نظرًا لأنه قد يكون هناك عدة وحدات ، وليس 1 ، فإن السؤال الذي يطرح نفسه هو أي بت واحد يجب أخذه لإيجاد اللوغاريتم. الإجابة هي رقم آخر بت واحد ، بدءًا من الجانب الأيمن من الرقم ، لأن أعلى قوة لاثنين هي التي تحدد الجزء الكامل من اللوغاريتم ، أما الباقي فيشكل الجزء الكسري من اللوغاريتم.



فكر في مثال آخر - رقم$$$45_{10} = 101101_2$... آخر بت واحد في الخانة الخامسة ، لذا فإن الجزء الصحيح من لوغاريتم 45 هو 5. وبالفعل$$$log_2(45)=5.4919$... نتجاهل الجزء الكسري ونترك 5.



كما أنه يعمل مع أرقام أخرى.



نتيجة لذلك ، حصلنا على أن الجزء الصحيح من اللوغاريتم يساوي عدد آخر بت واحد ، مع العد من اليمين. سؤال: كيف تجد رقم آخر بت؟



لهذا ، هناك وظائف تعتمد على عمليات البت ، والتي وجدتها في كتاب جي وارن "الحيل الخوارزمية للمبرمجين".

• التقريب إلى أس اثنين (أو إبراز آخر بت في التدوين الثنائي للرقم). في الواقع ، يمكنك التقريب ، ولكن بعد ذلك سيتم تقريب قيمة اللوغاريتم أيضًا.
• حساب عدد البتات المفردة في التدوين الثنائي لرقم

كلتا الوظيفتين موصوفتان جيدًا هناك ، وقد قدمت رمزهما مسبقًا.



باستخدام هاتين الوظيفتين ، تكون خوارزمية حساب الخوارزمية كما يلي:

1. حدد آخر بت واحد في الرقم. الآن تم كتابة الرقم كـ 100000
2. اطرح واحدًا من الرقم الناتج. ثم سيكون الرقم على هذا النحو: 011111
3. قم بحساب عدد وحدات بت وستكون هذه هي القيمة الصحيحة للوغاريتم

حالة استثنائية

اللوغاريتم لديه حالة استثنائية عندما x = 0. من الناحية النظرية ، مثل هذه الخوارزمية غير موجودة (أو في الحد يساوي -∞). ومع ذلك ، نظرًا لأننا ننحرف قليلاً عن قوانين الرياضيات في البرمجة ، فإن الوظائف لا تزال تعمل حتى عندما تكون مدخلات الدالة صفرًا. في هذه الحالة ، ستكون قيمة اللوغاريتم 32 (إذا كان الرقم 32 بت). يحدث هذا لأن دالة التقريب إلى أقرب أس لاثنين ستعطي 0 ، ثم نطرح واحدًا من الصفر ونحصل على الرقم 0xFFFFFFFF ، وهناك 32 وحدة في هذا الرقم ، وبالتالي سيكون اللوغاريتم 32.



نعم ، من وجهة نظر الرياضيات ، هذا غير صحيح ، ولكن هناك حالات ، عندما يكون مفيدًا من وجهة نظر البرمجة.

حساب طول الرمز الثنائي

من غير المحتمل أن يتم استخدام مثل هذه الوظيفة لحساب اللوغاريتم الرياضي ، لأن اللوغاريتمات غالبًا ما يتم اعتبارها من أرقام حقيقية ، وليس أعدادًا صحيحة.

ومع ذلك ، فإن حساب طول الشفرة الثنائية مهمة أكثر شيوعًا في الممارسة العملية.



دع رمزًا ثنائيًا بطول معين. يمكن أن يكون هذا ، على سبيل المثال ، مسارًا في شجرة ثنائية. إذا تمت كتابة بت واحد أمام هذا الرمز ، فمن الممكن حساب طول هذا الرمز دون استخدام المتغيرات المساعدة بأخذ لوغاريتم عدد صحيح.



على سبيل المثال ، دع الكود 0001110110 يتم كتابته ، على سبيل المثال ، في خلية من 32 بت وغالبًا ما نحتاج إلى قراءة طول هذا الرمز. للقيام بذلك ، قم بإضافة بت واحد إضافي قبل الرمز.



نحصل على: 10001110110. والآن يمكننا حساب طول هذا الرمز بأمان من خلال لوغاريتم العدد الصحيح ، دون تخزين طول هذا الرمز بشكل منفصل في مكان آخر.



إذا أخذنا في الاعتبار طول الكود ، حيث توجد جميع الأصفار ، فإن الوظيفة ستعيد الطول = 32 ، والذي قد يكون غير صحيح ، لذلك يجب توقع هذا الموقف. في بعض الحالات ، من المفيد أن تقوم الدالة بإرجاع 32 ، وفي حالات أخرى ، على سبيل المثال ، صفر.

المصادر

1. G. Warren الحيل الخوارزمية للمبرمجين. طبعة منقحة "، 2004