عد بت في عدد [مكررة]

Question

مكررة:

أفضل خوارزمية لحساب عدد من تعيين بت على 32 بت صحيحا ؟

---

افترض أن لديك عددا.هل هناك أي طريقة لحساب بت أي ما يعادل 1 في تمثيل ثنائي من هذا العدد ، وليس باستخدام تكرار ؟ أعني هل هناك أي طريقة للقيام بذلك في وقت ثابت باستخدام بعض المعامل مشغلي والأقنعة.أريد الحل الذي سوف تعمل بشكل جيد لكل من أبنية 32 بت و 64 بت.آه نسيت أنا في حاجة إليها على لغة C أو المجمع هو أيضا جيدة.

Answer 1

وهناك خوارزمية قليلا عد دون حلقة في HTTP: //graphics.stanford. ايدو / ~ seander / bithacks.html . الكثير من خوارزميات الفرز قليلا في HTTP: //gurmeetsingh.wordpress كوم / 2008/08/05 / بسرعة بت العد الروتينية /

Answer 2

بالطبع هناك ، ولكن أنت لن ترغب في ذلك.

يمكنك بالطبع بناء جدول بحث مع جميع القيم الصحيحة في ذلك:

الجدول[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

Answer 3

نعم، يمكنك القيام بذلك عن طريق استخدام rel="nofollow جدول البحث .