كيف يمكنني حساب عدد البتات الصفر في عدد صحيح؟

Question

كيف يمكنني العثور على عدد البتات "صفر" في C ++. لنفترض أن لدي عدد صحيح.

int value = 276; 

الذي لدي البتات 100010100 ، ولكن كيف يمكنني حساب الأصفار؟

Answer 1

أسهل طريقة سذاجة هي التكرار فقط على البتات والعد:

size_t num_zeroes = 0;

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i)
{
  if ((value & (1 << i)) == 0)
    ++num_zeroes;
}

هناك كل عدد من الطرق الأفضل (لقيم مختلفة من "أفضل") ، ولكن هذا واضح للغاية ، وذوقه للغاية (رمز) ، ولا يتطلب مجموعة من الإعداد.

يتمثل أحد التحسينات الصغيرة التي قد تعتبر تحسناً في عدم حساب القناع لاختبار كل بت ، بدلاً من ذلك قم بتحويل القيمة واختبر دائمًا بت أقصى اليمين:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1)
{
  if ((value & 1) == 0)
    ++num_zeroes;
}

Answer 2

إذا كنت تريد الكفاءة ، فهناك تطبيق جيد في كتاب "Hackers Delight"

22 تعليمات فرع الحرة.

unsigned int count_1bits(unsigned int x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

unsigned int count_0bits(unsigned int x)
{
    return 32 - count_1bits(x);
}

سأحاول شرح كيف يعمل. إنها خوارزمية الفجوة والقهر.

(x >> 1) & 0x55555555

يحول جميع البتات 1 خطوة إلى اليمين ويأخذ أقل جزء من كل زوج مهم.

0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs)

لذلك سيكون لديك في الأساس الجدول التالي لجميع التباديل 2 بت.

1. (00 >> 1) & 01 = 00
2. (01 >> 1) & 01 = 00
3. (10 >> 1) & 01 = 01
4. (11 >> 1) & 01 = 01

x - ((x >> 1) & 0x55555555);

ثم تقوم بطرحها من الأزواج غير المتغيرة.

1. 00 - 00 = 00 => 0 x 1 bits
2. 01 - 00 = 01 => 1 x 1 bits
3. 10 - 01 = 01 => 1 x 1 bits
4. 11 - 01 = 10 => 2 x 1 bits

x = x - ((x >> 1) & 0x55555555);

حتى الآن ، قمنا بتغيير كل زوج 2 بت ، بحيث تكون قيمتها الآن عدد أجزاء الأزواج الأصلية المقابلة 2 بت ... ثم نستمر بطريقة مماثلة مع 4 مجموعات ومجموعات 8 بت ومجموعات 16 بت ونهائية 32 بت.

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

Answer 3

يمكنك أن تفعل 32 ناقص عدد البتات المحددة.

Answer 4

إذا كنت تستخدم GCC ، يمكنك تجربة وظائف مدمجة:

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x)
int __builtin_clz (unsigned int x)

يرى وثائق مجلس التعاون الخليجي للتفاصيل.

Answer 5

طريق كيرنغان من عدد البتات المحددة

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

يمكن تكييفها بسهولة للمهمة المقدمة. عدد من التكرارات هنا يساوي عدد من البتات.

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

Answer 6

إلى حد بعيد الحل الأكثر وضوحًا هو جدول بحث.

/* Assuming CHAR_BITS == 8 */
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ };
int bitsInByte(unsigned char c) { return bits[c]; }

Answer 7

هناك كتاب رائع لهذا النوع من الأشياء: فرحة المتسلل (نعم ، الاسم تمتص: لا علاقة له بالأمان ولكن على وجه الحصر إلى البت). يوفر العديد من الخوارزميات لحساب "1" بت ، يمكن أيضًا العثور على الأفضل هنا (على الرغم من أن الكتاب لديه تفسيرات بأن هذا الموقع لا).

بمجرد أن تعرف عدد البتات "1" ، ما عليك سوى طرحه على عدد البتات في تمثيل النوع الخاص بك.

Answer 8

أنا مندهش لم يذكر أحد هذا:

int num_zero_bits = __builtin_popcount(~num);

هذا سوف يعطي عدد البتات الصفر في num عند استخدامها مع مجلس التعاون الخليجي.

Answer 9

قم بإثبات المرء ثم عد 1s.

count_zero_bits (x) = count_one_bits (~ x) ؛

تنفيذ الرمز لحساب تلك.

template< typename I > 
int count_one_bits( I i )
{
   size_t numbits = 0;
   for( ; i != 0; i >>= 1 )
   {
      numbits += i&1;
   }
}

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

بمجرد أن تحصل على ذلك:

template< typename I > int count_zero_bits( I i )
{
   return count_one_bits( ~i );
}

سيعمل.

Answer 10

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

int get_zero_bit_count(int num)
{
    int cnt = 0;

    while(num > 0)
        {
            int and_num = num & 1;

            if (and_num != num) cnt++;

            num >>= 1; 
        }

        return cnt;
    }

من السهل فهم قطعة الكود هذه وتوضيح SELP. هذا يعمل بشكل جيد للأعداد الصحيحة الإيجابية.

Answer 11

التوسع في إجابة Ronag ، والتي ذكرها المستخدمون الآخرون يؤدي إلى نتائج خاطئة (تعمل خوارزميةه فقط على قيمة x = 15) ، إليك نسخة محدثة من الخوارزمية:

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

uint8_t count_0bits(uint32_t x)    {
    return 32 - count_1bits(x);
}

إن شرح السطر الأول من Ronag صحيح ، ومع ذلك ، فإن الخطوط المتبقية تستخدم نهجًا مختلفًا. في السطر الأول ، من خلال التحول والطرح ، سيحتوي كل زوج من 2 بت على عدد البتات التي تم تعيينها في هذا الزوج في الرقم الأصلي. تطوي بقية الخطوط هذه الأرقام معًا عن طريق إضافة LSB لكل مجموعة 2N-bit إلى MSB لهذا الزوج الذي تم تحويله بواسطة N ، بحيث تحتوي المجموعة 2N-Bit على عدد البتات التي تم تعيينها في تلك المجموعة في تلك المجموعة الرقم الأصلي:

01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number)
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111
= 0110 + 0111
= 1101

تعمل الخوارزمية المذكورة أعلاه لأعداد صحيحة 32 بت ، ولكن يمكن تكييفها بسهولة عن طريق تغيير الثوابت إلى طول البت الصحيح بحيث يبقى النمط كما هو (على سبيل المثال 0x555 ... = 0101 ... ، 0x0f0f ... = 00001111. .. إلخ) وإضافة/إزالة التحولات المناسبة