ما هي أسرع طريقة لحساب عدد البتات اللازمة لتخزين رقم

Question

أحاول تحسين بعض التعبئة وتفريغ الروتين. من أجل القيام بالتعبئة ، أحتاج إلى حساب عدد البتات اللازمة لتخزين قيم عدد صحيح. هنا هو الرمز الحالي.

if (n == -1) return 32;
if (n == 0) return 1;
int r = 0;
while (n)
{
    ++r;
    n >>= 1;
}
return r;

Answer 1

أنت تتطلع إلى تحديد قاعدة سجل عدد صحيح 2 من الرقم (L = أعلى مجموعة بت). تحتوي صفحة Sean Anderson "Bit Twiddling Hacks" على العديد من الطرق التي تتراوح من أجزاء العد الواضحة في حلقة إلى الإصدارات التي تستخدم بحث الجدول. لاحظ أن معظم الأساليب التي تم توضيحها ستحتاج إلى تعديل بعض الشيء للعمل مع INTs 64 بت إذا كان هذا النوع من قابلية النقل مهمًا بالنسبة لك.

• http://graphics.stanford.edu/~seander/bithacks.html#integerlogobvious

فقط تأكد من أن أي تحول تستخدمه للعمل على أعلى مجموعة يجب القيام به "على unsigned إصدار الرقم نظرًا لأن تطبيق المترجم قد يوقع أو لا يوقع >> العملية على قيمة موقعة.

Answer 2

غير محتفظ ، استخدم رمز البت المفصلي المتاح على معظم البنى الحديثة. إنه مكشوف ك حقيقي في Visual C ++.

بشكل ملحوظ ، لا يحتاج الرمز في السؤال إلى معالجة حالة الحافة. لماذا تحتاج بت واحد لتخزين 0؟ في أي حال ، سأتجاهل حواف المشكلة. يمكن إجراء الشجاعة بكفاءة:

if (n >> 16) { r += 16; n >>= 16; }
if (n >>  8) { r +=  8; n >>=  8; }
if (n >>  4) { r +=  4; n >>=  4; }
if (n >>  2) { r +=  2; n >>=  2; }
if (n - 1) ++r;

Answer 3

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

قم بإنشاء جدول من 256 إدخالات ، حيث يحدد كل عنصر الجزء العلوي الأكثر.

إما حلقة من خلال كل بايت في الرقم ، أو استخدم بعض الاختبارات IF لكسر للعثور على أعلى ترتيب غير صفري.

سأدعك تأخذ الباقي من هنا.

Answer 4

قم بالبحث الثنائي بدلاً من البحث الخطي.

if ((n >> 16) != 0)
{
    r += 16;
    n >>= 16;
}

if ((n >> 8) != 0)
{
    r += 8;
    n >>= 8;        
}

if ((n >> 4) != 0)
{
    r += 4;
    n >>= 4;        
}

// etc.

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

#ifdef ARCHITECTURE_WITH_BSR
   asm // ...
#else
   // Use the approach shown above
#endif

Answer 5

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

if (n < 0) return 32;
int r = 0;
while (n && 0x7FFFFFF0) {
  r+=4;
  n >>= 4; }
while (n) {
  r++;
  n >>= 1; }
return r;

Answer 6

number_of_bits = log2(integer_number)

تقريب إلى عدد صحيح أعلى.