رمز C لحساب عدد البتات "1" في شار غير موقعة

Question

أحتاج إلى رمز C لإرجاع عدد 1 في char غير موقعة في C. أحتاج إلى شرح حول سبب عمله إذا لم يكن واضحًا. لقد وجدت الكثير من التعليمات البرمجية لرقم 32 بت ولكن ليس كثيرًا بالنسبة إلى Char غير موقعة.

Answer 1

نفس الرمز سيعمل لشار غير موقعة. حلقة على جميع البتات لاختبارها. نرى هذه.

Answer 2

const unsigned char oneBits[] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};

unsigned char CountOnes(unsigned char x)
{
    unsigned char results;
    results = oneBits[x&0x0f];
    results += oneBits[x>>4];
    return results
}

احصل على صفيف يعرف عدد البتات من 0 إلى 15. أضف النتائج لكل حلقة.

Answer 3

Hackmem لديه هذه الخوارزمية في 3 عمليات (ترجمت تقريبًا إلى ج):

bits = (c * 01001001001ULL & 042104210421ULL) % 017;

(ULL هو إجبار 64 بت. هناك حاجة ، فقط بالكاد ... هذا الحساب يتطلب أعداد صحيحة 33 بت.)

في الواقع ، يمكنك استبدال الثابت الثاني مع 042104210021ULL, نظرًا لأنك تحسب 8 بتات فقط ، لكنها لا تبدو متناظرة بشكل جيد.

كيف يعمل هذا؟ افكر في c قليلا من الحكمة ، وتذكر ذلك (a + b) % c = (a % c + b % c) % c, ، و (a | b) == a + b IFF (a & b) == 0.

  (c * 01001001001ULL & 042104210421ULL) % 017
  01   01001001001                01         1
  02   02002002002       02000000000         1
  04   04004004004          04000000         1
 010  010010010010            010000         1
 020  020020020020               020         1
 040  040040040040      040000000000         1  # 040000000000 == 2 ** 32
0100 0100100100100        0100000000         1
0200 0200200200200           0200000         1

إذا لم يكن لديك حساب 64 بت متاح ، فيمكنك الانقسام c حتى في قرارات وافعل كل نصف ، مع 9 عمليات. هذا يتطلب فقط 13 بت ، لذلك سيعمل استخدام الحساب 16 أو 32 بت.

bits = ((c & 017) * 0421 & 0111) % 7 + ((c >> 4) * 0421 & 0111) % 7;

(c * 0421 & 01111) % 7
 1   0421      01    1
 2  01042   01000    1
 4  02104    0100    1
 8  04210     010    1

على سبيل المثال ، إذا c == 105 == 0b11001001,

c == 0100
   |  040
   |  010
   |   01 == 0151
* 01001001001001ULL == 0100100100100
                     |  040040040040
                     |  010010010010
                     |   01001001001 == 0151151151151
& 0421042104210421ULL ==  0100000000
                       | 04000000000
                       |      010000
                       |          01 ==   04100010001
% 017                                == 4

c & 017      ==            8 | 1           ==                   011
011 * 0421   ==     8 * 0421 | 1 * 0421    == 04210 | 0421 == 04631
04631 & 0111 == 04210 & 0111 | 0421 & 0111 ==   010 | 01   ==   011
011 % 7      == 2

c >> 4       ==            4 | 2            ==                     06
06 * 0421    ==     4 * 0421 | 2 * 0421     == 02104 | 01042 == 03146
03146 & 0111 == 02104 & 0111 | 01042 & 0111 ==  0100 | 01000 == 01100
01100 % 7    == 2

2 + 2 == 4

Answer 4

شاهد صفحة Bit Twiddling Hacks: http://graphics.stanford.edu/~seander/bithacks.html#countbitssetkernighan

هناك العديد من الحلول الجيدة لهذا الغرض.

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

Answer 5

للحصول على عدد صحيح صغير مثل Char غير موقعة ، تحصل على أفضل أداء باستخدام جدول بحث صغير.

أعرف ما هي خوارزميات العرف السكانية التي تذكرها. إنهم يعملون عن طريق إجراء حسابات متعددة أصغر من عدد صحيح مخزّن في السجل.

هذه التقنية تسمى سوار (http://en.wikipedia.org/wiki/swar).

لمزيد من المعلومات ، أقترح عليك التحقق من موقع Hackers Delight: www.hackersdelight.org. لديه مثال رمز وكتب كتابًا يشرح هذه الحيل بالتفصيل.

Answer 6

كما تم الإجابة عليه بالفعل ، تعمل الطرق القياسية لحساب البتات أيضًا على chars غير الموقعة.

مثال:

    unsigned char value = 91;
int bitCount = 0;
while(value > 0)
{
    if ( value & 1 == 1 ) 
        bitCount++;
    value >>= 1;
}

Answer 7

إن char غير موقّع هو "رقم" بنفس الطريقة التي يكون بها تعويم 32 بت أو عدد صحيح هو "رقم" ، ما يراه المترجم لهم هو ما يتغير.

إذا قمت بتصوير شار على أنه أجزاء له:

01010011 (8 بت) ؛

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

خذ القيمة ، دعنا نقول x ، واتخاذ x ٪ 2 ، سيكون الباقي إما 1 أو 0. وهذا ، اعتمادًا على endianness من char ، اليسار أو اليمين الأكثر بت. تراكم الباقي في متغير منفصل (سيكون هذا هو العدد الناتج من البتات المحددة).

ثم >> (التحول الأيمن) 1 بت.

كرر حتى تم تحويل 8 بت.

يجب أن يكون رمز C بسيطًا جدًا للتنفيذ من الرمز الكاذب الخاص بي ، ولكن بشكل أساسي

public static int CountSetBits(char c)
{
    int x = 0;
    int setBits = 0;
    while (x < 7)
    {
       setBits = setBits + c % 2;
       c = c >> 1;
       x = x + 1;
    }
}

Answer 8

قاعدة على منشور ephemient ، لدينا إصدار 8 بتات متفرعة. إنه في تعبير سداسي عشري.

typedef unsigned char       UINT8;
typedef unsigned short      UINT16;
typedef unsigned long long  UINT64;
int hammingWeight8( const UINT8& c)
{
    return ( c* 0x8040201ULL & 0x11111111)%0xF;
}

قم بتطبيقه مرتين ، ولدينا نسخة 16Bits ، والتي تحتاج إلى 9 عمليات.

int hammingWeight16( const UINT16& c)
{
    return ((c & 0xFF)* 0x8040201ULL & 0x11111111)%0xF + 
             ((c >> 8)* 0x8040201ULL & 0x11111111)%0xF;
}

أنا هنا أكتب نسخة 16Bits المتغيرة التي تحتاج إلى 64Bits سجلات و 11 عملية. يبدو أنه ليس أفضل من العملية السابقة ، ولكنه يستخدم فقط عملية Modulo واحدة.

int hammingWeight16( const UINT16& c)
{
    UINT64  w;
    w= (((( c* 0x8000400020001ULL)>> 3) & 0x1111111111111111)+14)%0xF;
    return (c!=0)*(w+1+(c==0xFFFF)*15);
}