عد بت في عدد [مكررة]
-
20-08-2019 - |
سؤال
مكررة:
افترض أن لديك عددا.هل هناك أي طريقة لحساب بت أي ما يعادل 1 في تمثيل ثنائي من هذا العدد ، وليس باستخدام تكرار ؟ أعني هل هناك أي طريقة للقيام بذلك في وقت ثابت باستخدام بعض المعامل مشغلي والأقنعة.أريد الحل الذي سوف تعمل بشكل جيد لكل من أبنية 32 بت و 64 بت.آه نسيت أنا في حاجة إليها على لغة C أو المجمع هو أيضا جيدة.
المحلول
وهناك خوارزمية قليلا عد دون حلقة في HTTP: //graphics.stanford. ايدو / ~ seander / bithacks.html . الكثير من خوارزميات الفرز قليلا في HTTP: //gurmeetsingh.wordpress كوم / 2008/08/05 / بسرعة بت العد الروتينية /
نصائح أخرى
بالطبع هناك ، ولكن أنت لن ترغب في ذلك.
يمكنك بالطبع بناء جدول بحث مع جميع القيم الصحيحة في ذلك:
الجدول[1] = 1 الجدول[2] = 1 الجدول[3] = 2,.... الخ
لذلك هذا سوف تعطيك سريع حقا الجواب, لكنه عديمة الفائدة تماما الحل في حد ذاته ، منذ الطاولة يجب أن تكون كبيرة جدا.
هل يمكن تحسين هذا قليلا ، ولكنه يتطلب فقط القليل من التكرار.ببساطة إنشاء 8-بت من الجدول الحل مجرد 256-إدخال الجدول ، ثم تكرار عبر كل بايت في القيمة إلى أن يتم التحقق ، تلخيص نتائج طاولة البحث.شيء من هذا القبيل:
short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
result += tableLookup[ (valueToCheck & 0xFF) ];
valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.
همم, يبدو أن هذا هو معروف (و هنا كنت تفعل هذا من قمة رأسي):http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
نعم، يمكنك القيام بذلك عن طريق استخدام rel="nofollow جدول البحث .