كيف نحسب عدد من تعيين بت على 32 بت صحيحا ؟
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
8 بت تمثل عدد 7 تبدو مثل هذا:
00000111
ثلاثة أجزاء يتم تعيين.
ما هي خوارزميات لتحديد عدد من تعيين بت على 32 بت صحيحا ؟
المحلول
هذا هو المعروف باسم 'المبالغة الوزن', 'popcount' أو 'جانبية بالإضافة إلى ذلك'.
'أفضل' خوارزمية حقا يتوقف على وحدة المعالجة المركزية التي أنت على ما بك استخدام النمط.
بعض وحدات المعالجة المركزية واحدة المدمج في التدريس للقيام بذلك والبعض الآخر الموازي التعليمات التي تعمل على بعض النواقل.موازية تعليمات (مثل x86 هو popcnt, على وحدات المعالجة المركزية حيث انها معتمدة) يكاد يكون من المؤكد سوف يكون أسرع.بعض أبنية قد يكون بطيئا تعليمات تنفيذها مع microcoded حلقة اختبارات قليلا في دورة (بحاجة لمصدر).
ما قبل بالسكان طاولة بحث الطريقة يمكن أن تكون سريعة جدا إذا كانت وحدة المعالجة المركزية الخاصة بك كبيرة ذاكرة التخزين المؤقت و/أو كنت تفعل الكثير من هذه التعليمات في حلقة ضيقة.ومع ذلك يمكن أن يعاني بسبب حساب 'ملكة جمال مخبأ', حيث وحدة المعالجة المركزية قد جلب بعض من الجدول من الذاكرة الرئيسية.
إذا كنت تعرف أن لديك بايت سيكون في الغالب 0 أو معظمها 1 ثم هناك خوارزميات فعالة لهذه السيناريوهات.
وأعتقد جيد جدا للأغراض العامة الخوارزمية التالية ، المعروفة باسم 'موازية" أو "متغير الدقة مصنع سوار خوارزمية'.وقد أعربت عن ذلك في ج-مثل الزائفة اللغة, قد تحتاج إلى ضبط العمل لغة معينة (مثلا ، باستخدام uint32_t عن C++ > > > في جاوة):
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
هذا أفضل أسوأ سلوك أي من الخوارزميات التي نوقشت ، لذلك سيتم التعامل بكفاءة مع أي نمط الاستخدام أو القيم التي يمكنك رمي في ذلك.
هذا المعامل-مصنع سوار خوارزمية يمكن أن يوازي ينبغي القيام به في عدة عناصر مكافحة ناقلات في وقت واحد بدلا من واحد صحيح السجل ، من أجل تسريع على وحدات المعالجة المركزية مع SIMD ولكن لا للاستخدام popcount التعليمات.(مثلا ، x86-64 البرمجية التي يجب أن تعمل على أي وحدة المعالجة المركزية ، ليس فقط Nehalem أو في وقت لاحق.)
ومع ذلك ، فإن أفضل طريقة لاستخدام ناقل تعليمات popcount عادة باستخدام متغير-خلط للقيام الجدول-بحث عن 4 بت في الوقت من كل بايت في نفس الوقت.(4 بت مؤشر 16 إدخال الجدول الذي عقد في ناقلات التسجيل).
على إنتل وحدات المعالجة المركزية, الأجهزة 64bit popcnt التعليمات يمكن أن يتفوق أحد SSSE3 PSHUFB بت التنفيذ المتوازي قبل حوالي عامل 2 ، ولكن فقط إذا كان المترجم الخاص بك يحصل على ذلك الحق فقط.وإلا SSE يمكن أن يخرج بفارق كبير.أحدث الإصدارات المحول البرمجي على بينة من popcnt كاذبة التبعية المشكلة على Intel.
المراجع:
https://graphics.stanford.edu/~seander/bithacks.html
https://en.wikipedia.org/wiki/Hamming_weight
http://gurmeet.net/puzzles/fast-bit-counting-routines/
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(منها%20Count)
نصائح أخرى
تنظر أيضا المدمج في وظائف المجمعين.
على GNU compiler على سبيل المثال يمكنك فقط استخدام:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
في أسوأ الأحوال المترجم سوف تولد استدعاء دالة.في أفضل الأحوال المترجم تنبعث من وحدة المعالجة المركزية تعليمات للقيام بنفس المهمة بشكل أسرع.
دول مجلس التعاون الخليجي إينترينسيكس حتى تعمل عبر منصات متعددة.Popcount أصبح الاتجاه السائد في الهندسة المعمارية x86, لذلك فمن المنطقي أن تبدأ باستخدام الجوهرية الآن.غيرها من أبنية يكون popcount لسنوات.
على x86 يمكنك أن تخبر المترجم أنه يمكن أن نفترض دعم popcnt التعليمات مع -mpopcnt أو -msse4.2 أيضا تمكين ناقل التعليمات التي أضيفت في نفس الجيل.انظر دول مجلس التعاون الخليجي إلى x86 الخيارات. -march=nehalem (أو -march= مهما وحدة المعالجة المركزية كنت تريد الخاص بك رمز لتولي إلى لحن) يمكن أن يكون خيارا جيدا.تشغيل الناتجة الثنائية على وحدة المعالجة المركزية القديمة سيؤدي في غير قانونية-تعليمات خطأ.
لجعل الثنائيات الأمثل آلة بناء عليها ، -march=native (مع دول مجلس التعاون الخليجي, رنة, أو المحكمة الجنائية الدولية).
MSVC يوفر جوهرية بالنسبة إلى x86 popcnt التعليمات, ولكن على عكس دول مجلس التعاون الخليجي انها حقا أساسيا للأجهزة التعليمات و يتطلب دعم الأجهزة.
باستخدام std::bitset<>::count() بدلا من المدمج في
في نظرية, أي مترجم أن يعرف كيف popcount بكفاءة الهدف وحدة المعالجة المركزية يجب فضح هذه الوظيفة من خلال ISO C++ std::bitset<>.في الواقع ، قد تكون أفضل حالا مع بت هاك/التحول/ADD في بعض الحالات لبعض الهدف وحدات المعالجة المركزية.
الهدف أبنية حيث الأجهزة popcount ملحق اختياري (مثل x86) ليس كل المجمعين لها std::bitset أن يستفيد من ذلك عندما تكون متاحة.على سبيل المثال ، MSVC لا يوجد لديه وسيلة لتمكين popcnt الدعم في وقت الترجمة ، و يستخدم دائما جدول البحث, حتى مع /Ox /arch:AVX (مما يعني SSE4.2, على الرغم من الناحية الفنية هناك ميزة منفصلة بت popcnt.)
ولكن على الأقل يمكنك الحصول على شيء المحمولة التي تعمل في كل مكان و مع دول مجلس التعاون الخليجي/رنة مع الهدف الصحيح الخيارات يمكنك الحصول على الأجهزة popcount عن البنى التي تدعم ذلك.
#include <bitset>
#include <limits>
#include <type_traits>
template<typename T>
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned<T>::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset<bitwidth> bs( static_cast<UT>(x) );
return bs.count();
}
انظر asm من دول مجلس التعاون الخليجي, رنة, المحكمة الجنائية الدولية, و MSVC على Godbolt مترجم explorer.
x86-64 gcc -O3 -std=gnu++11 -mpopcnt تنبعث من هذا:
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret
PowerPC64 gcc -O3 -std=gnu++11 تنبعث (عن int arg الإصدار):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
هذا المصدر ليس x86 محددة أو جنو محددة في كل شيء ، ولكن فقط يجمع جيدا x86 مع دول مجلس التعاون الخليجي/رنة/المحكمة الجنائية الدولية.
نلاحظ أيضا أن دول مجلس التعاون الخليجي تراجع عن أبنية دون واحد التعليمات popcount هو بايت في وقت طاولة البحث.هذا ليس رائع ذراع, على سبيل المثال.
في رأيي, أفضل حل هو واحد التي يمكن قراءتها من جانب آخر مبرمج (أو المبرمج الأصلي عامين) دون غزير التعليقات.قد ترغب أسرع أو أذكى حل بعض قدمت بالفعل ولكن أنا أفضل قراءة أكثر ذكاء في أي وقت.
unsigned int bitCount (unsigned int value) {
unsigned int count = 0;
while (value > 0) { // until all bits are zero
if ((value & 1) == 1) // check lower bit
count++;
value >>= 1; // shift bits, removing lower bit
}
return count;
}
إذا كنت تريد المزيد من السرعة (وعلى افتراض انك الوثيقة جيدا للمساعدة الخاصة بك خلفاء), هل يمكن استخدام طاولة البحث:
// Lookup table for fast calculation of bits set in 8-bit unsigned char.
static unsigned char oneBitsInUChar[] = {
// 0 1 2 3 4 5 6 7 8 9 A B C D E F (<- n)
// =====================================================
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
: : :
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};
// Function for fast calculation of bits set in 16-bit unsigned short.
unsigned char oneBitsInUShort (unsigned short x) {
return oneBitsInUChar [x >> 8]
+ oneBitsInUChar [x & 0xff];
}
// Function for fast calculation of bits set in 32-bit unsigned int.
unsigned char oneBitsInUInt (unsigned int x) {
return oneBitsInUShort (x >> 16)
+ oneBitsInUShort (x & 0xffff);
}
على الرغم من أن هذه تعتمد على بيانات محددة نوع الأحجام حتى انهم لا أن المحمولة.ولكن لأن العديد من أمثلية الأداء لم يكن محمول على أي حال, هذا قد لا يكون مشكلة.إذا كنت تريد قابلية كنت عصا للقراءة الحل.
int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
ينفذ في ~20 العش تعليمات (قوس تعتمد) لا المتفرعة.
هاكر فرحة هو لذيذ!موصى به للغاية.
أعتقد أن أسرع طريقة بدون استخدام جداول البحث ، popcount—هو ما يلي.وتعول تعيين بت مع فقط 12 العمليات.
int popcount(int v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
يعمل لأنك يمكن أن تعول على عدد من تعيين بت من خلال تقسيم في اثنين نصفين ، عد عدد من البتات في كل شطر ثم إضافة لهم.تعرف أيضا باسم Divide and Conquer النموذج.دعونا ندخل في التفاصيل..
v = v - ((v >> 1) & 0x55555555);
عدد البتات في اثنين بت يمكن 0b00, 0b01 أو 0b10.يتيح محاولة عمل ذلك على 2 بت..
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
هذا هو المطلوب:العمود الأخير يظهر العد تعيين بت في كل اثنين بت الزوج.إذا كان اثنين بت رقم >= 2 (0b10) ثم and تنتج 0b01, وإلا فإنه ينتج 0b00.
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
هذا البيان يجب أن يكون من السهل أن نفهم.بعد العملية الأولى لدينا عدد من القطع في كل اثنين بت, الآن نحن نلخص أن الاعتماد في كل 4 بت.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
نحن ثم نلخص النتيجة أعلاه تعطينا إجمالي عدد من تعيين بت 4 بت.البيان الأخير هو الأكثر صعبة.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
دعونا كسر مزيد من...
v + (v >> 4)
انها مماثلة الثاني البيان ؛ ونحن نعول على تعيين بت في مجموعات من 4 بدلا من ذلك.ونحن نعلم—بسبب العمليات السابقة—أن كل عاب لديه عدد من تعيين بت في ذلك.دعونا ننظر على سبيل المثال.لنفترض أن لدينا بايت 0b01000010.يعني أول من عاب لها 4bits مجموعة والثاني له 2bits مجموعة.الآن نضيف تلك يقضم معا.
0b01000010 + 0b01000000
أنه يعطي لنا عدد من البتات في البايت الأول عاب 0b01100010 وبالتالي نحن قناع آخر أربعة بايت من كل بايت في عدد (التخلص منها).
0b01100010 & 0xF0 = 0b01100000
الآن كل بايت يحتوي على عدد من تعيين بت في ذلك.نحن بحاجة إلى إضافة لهم جميعا معا.الحيلة هي أن مضاعفة النتيجة عن طريق 0b10101010 الذي مثيرة للاهتمام الملكية.إذا كان لدينا عدد أربعة بايت ، A B C D, أن ذلك سيؤدي إلى رقم جديد مع هذه بايت A+B+C+D B+C+D C+D D.4 بايت عدد يمكن أن يكون الحد الأقصى من 32 بت التي يمكن أن تكون ممثلة على النحو 0b00100000.
كل ما نحتاجه الآن هو البايت الأول الذي يحتوي على مجموع من كل مجموعة بت في كل بايت, و نحصل عليه عن طريق >> 24.هذه الخوارزمية تم تصميمه 32 bit الكلمات ولكن يمكن تعديلها بسهولة عن 64 bit كلمات.
إذا كنت يحدث ليكون باستخدام جافا, المدمج في طريقة Integer.bitCount سوف تفعل ذلك.
شعرت بالملل و توقيت مليار التكرار من ثلاثة اتجاهات.المترجم هو دول مجلس التعاون الخليجي -O3.وحدة المعالجة المركزية هو ما وضعوا في 1st الجنرال ماك بوك برو.
الأسرع هو التالي في 3.7 ثانية:
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}
المركز الثاني يذهب إلى نفس الكود ولكن يبحث حتى 4 بايت بدلا من 2 halfwords.الذي استغرق حوالي 5.5 ثانية.
المركز الثالث يذهب إلى بت twiddling 'جانبية إضافة' النهج الذي استغرق 8.6 ثواني.
المركز الرابع يذهب إلى دول مجلس التعاون الخليجي __مدمج_popcount () في مخجل 11 ثانية.
عد بت واحد في وقت النهج waaaay أبطأ ، لقد مللت من الانتظار حتى يكتمل.
لذلك إذا كنت تهتم الأداء قبل كل شيء ثم استخدام النهج الأول.إذا كنت الرعاية ، ولكن ليس بما فيه الكفاية لقضاء 64Kb من ذاكرة الوصول العشوائي على ذلك ، استخدام النهج الثاني.وإلا تستخدم للقراءة (ولكن بطيئة) بت واحد في وقت النهج.
من الصعب التفكير في الحالة التي تكون فيها كنت ترغب في استخدام بت twiddling النهج.
تحرير:نتائج مماثلة هنا.
unsigned int count_bit(unsigned int x)
{
x = (x & 0x55555555) + ((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;
}
اسمحوا لي أن أشرح هذه الخوارزمية.
هذه الخوارزمية على أساس فرق تسد الخوارزمية.لنفترض أن هناك 8bit صحيح 213(11010101 في الثنائية) ، خوارزمية يعمل مثل هذا(في كل مرة دمج اثنين من الجيران بنات):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
هذا هو واحد من تلك الأسئلة حيث أنه يساعد على معرفة الهندسة المعمارية الدقيقة.أنا فقط توقيت اثنين من المتغيرات في إطار دول مجلس التعاون الخليجي 4.3.3 جمعت مع -O3 باستخدام C++ inlines للقضاء على استدعاء دالة النفقات العامة ، مليار التكرار ، والحفاظ على مجموع تراكمي من جميع التهم لضمان المترجم لا إزالة أي شيء مهم ، وذلك باستخدام rdtsc عن توقيت (ساعة دورة دقيقة).
inline int pop2(unsigned x, unsigned y)
{
x = x - ((x >> 1) & 0x55555555);
y = y - ((y >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
return (x+y) & 0x000000FF;
}
معدلة هاكر فرحة أخذت 12.2 gigacycles.بلدي موازية الإصدار (عد ضعف عدد البتات) يعمل في 13.0 gigacycles.10.5 s مجموع المنقضي على حد سواء معا على 2.4 GHz Core Duo.25 gigacycles = أكثر من 10 ثوان في هذا تردد على مدار الساعة, لذلك أنا واثق من بلدي الأوقات الصحيحة.
هذا له علاقة مع تعليمات الاعتماد السلاسل التي هي سيئة جدا على هذه الخوارزمية.يمكنني أن ما يقرب من ضعف السرعة مرة أخرى باستخدام زوج من 64 بت السجلات.في الواقع, إذا كنت ذكي وأضاف x+y قليلا عاجلا يمكنني أن يحلق بعض التحولات.الإصدار 64 بت مع بعض التعديلات من شأنه أن يخرج عن ذلك ، ولكن العد مرتين العديد من القطع مرة أخرى.
مع 128 بت SIMD السجلات ، ولكن هناك عامل آخر من اثنين ، SSE مجموعات التعليمات في كثير من الأحيان يكون ذكي مختصرة أيضا.
لا يوجد سبب مدونة خاصة شفافة.واجهة بسيطة ، خوارزمية يمكن الرجوع إليها على الخط في العديد من الأماكن ، وانها قابلة شاملة اختبار الوحدة.مبرمج من الزلات حتى أنه قد تعلم شيئا.هذه العمليات قليلا للغاية الطبيعية على مستوى الجهاز.
حسنا قررت أن البدلاء أنب 64-بت.هذا sizeof(غير موقعة طويلة) == 8
inline int pop2(unsigned long x, unsigned long y)
{
x = x - ((x >> 1) & 0x5555555555555555);
y = y - ((y >> 1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0xFF;
}
الذي يبدو عن الحق (أنا لم تختبر بعناية ، على الرغم من).الآن توقيت الخروج في 10.70 gigacycles / 14.1 gigacycles.في وقت لاحق عدد لخص 128 مليار بت يتوافق مع 5.9 s المنقضي على هذا الجهاز.غير موازية النسخة يسرع قليلا لأنني تشغيل في وضع 64 بت و يحب 64 بت يسجل أفضل قليلا من 32 بت السجلات.
دعونا نرى إذا كان هناك أكثر قليلا OOO pipelining قد يكون هنا.كان هذا أكثر قليلا من المشاركة, لذلك أنا في الواقع اختبار قليلا.كل مصطلح وحدها مبالغ 64 ، كلها مجتمعة مبلغ 256.
inline int pop4(unsigned long x, unsigned long y,
unsigned long u, unsigned long v)
{
enum { m1 = 0x5555555555555555,
m2 = 0x3333333333333333,
m3 = 0x0F0F0F0F0F0F0F0F,
m4 = 0x000000FF000000FF };
x = x - ((x >> 1) & m1);
y = y - ((y >> 1) & m1);
u = u - ((u >> 1) & m1);
v = v - ((v >> 1) & m1);
x = (x & m2) + ((x >> 2) & m2);
y = (y & m2) + ((y >> 2) & m2);
u = (u & m2) + ((u >> 2) & m2);
v = (v & m2) + ((v >> 2) & m2);
x = x + y;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
x = x + u;
x = x + (x >> 8);
x = x + (x >> 16);
x = x & m4;
x = x + (x >> 32);
return x & 0x000001FF;
}
كنت متشوقة للحظة, ولكن اتضح دول مجلس التعاون الخليجي دورا مضمنة الحيل مع -O3 على الرغم من أنني لست باستخدام مضمنة الكلمة في بعض الاختبارات.عندما سمحت دول مجلس التعاون الخليجي تلعب الحيل مليار يدعو إلى pop4() يأخذ 12.56 gigacycles لكني قررت بأنها قابلة للطي الحجج المستمر التعبيرات.أكثر واقعية ويبدو أن عددا 19.6 gc لمدة 30% من السرعة-التي تصل.اختباري حلقة تبدو الآن مثل هذا ، والتأكد من أن كل حجة مختلفة بما فيه الكفاية لوقف دول مجلس التعاون الخليجي من اللعب الحيل.
hitime b4 = rdtsc();
for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i)
sum += pop4 (i, i^1, ~i, i|1);
hitime e4 = rdtsc();
256 مليار بت لخص في 8.17 s المنقضي.يعمل بها إلى 1.02 s 32 مليون بت كأساس مرجعي في 16-بت طاولة البحث.لا يمكن مقارنة مباشرة ، لأن البدلاء لا تعطي السرعة على مدار الساعة ، ولكن يبدو أنني قد صفع المخاط من 64KB الجدول الطبعة ، وهو المأساوية استخدام L1 cache في المقام الأول.
تحديث:قررت أن تفعل واضحة وخلق pop6() بإضافة أربعة تكرار الخطوط.خرج إلى 22.8 gc, 384 مليار بت لخص في 9.5 ثانية المنقضي.لذلك هناك 20 ٪ أخرى الآن في 800ms 32 مليار بت.
لماذا لا تكراري القسمة على 2?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
أوافق على أن هذا ليس أسرع ، ولكن "أفضل" هو إلى حد ما غامضة.ويهمني القول على الرغم من أن "أفضل" يجب أن يكون عنصر الوضوح
الهاكر فرحة بت twiddling يصبح أكثر وضوحا عند كتابة بعض الأنماط.
unsigned int bitCount(unsigned int x)
{
x = ((x >> 1) & 0b01010101010101010101010101010101)
+ (x & 0b01010101010101010101010101010101);
x = ((x >> 2) & 0b00110011001100110011001100110011)
+ (x & 0b00110011001100110011001100110011);
x = ((x >> 4) & 0b00001111000011110000111100001111)
+ (x & 0b00001111000011110000111100001111);
x = ((x >> 8) & 0b00000000111111110000000011111111)
+ (x & 0b00000000111111110000000011111111);
x = ((x >> 16)& 0b00000000000000001111111111111111)
+ (x & 0b00000000000000001111111111111111);
return x;
}
الخطوة الأولى يضيف حتى بت إلى بت غريبة, إنتاج مبلغ من البتات في كل اثنين.الخطوات الأخرى إضافة عالية من أجل قطع منخفضة من أجل قطع, مضاعفة جزء حجم كل وسيلة تصل حتى يكون العدد النهائي تناول كامل int.
عن وسيلة سعيدة بين 232 جدول بحث و بالتكرار عبر كل بت على حدة:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
انها ليست أسرع أو أفضل حل ، ولكن وجدت نفس السؤال في طريقي, و بدأت أفكر و أفكر.وأخيرا أدركت أنه يمكن أن يتم مثل هذا إذا كنت تحصل على هذه المشكلة من الجانب الرياضي و رسم بياني, ثم تجد أنه من وظيفة التي لديها بعض الدورية جزءا ثم كنت أدرك الفرق بين الفترتين...حتى هنا تذهب:
unsigned int f(unsigned int x)
{
switch (x) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 1;
case 3:
return 2;
default:
return f(x/4) + f(x%4);
}
}
هذا يمكن القيام به في O(k), حيث k هو عدد البتات مجموعة.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
وظيفة كنت تبحث عن وغالبا ما تسمى "جانبية مبلغ" أو "عدد السكان" من رقم ثنائي.كانوث يناقش ذلك في مرحلة ما قبل كراسة 1A, pp11-12 (على الرغم من أن هناك إشارة موجزة في المجلد 2 ، 4.6.3-(7).)
على موضع classicus بيتر Wegner المادة "تقنية عد منها في الكمبيوتر ثنائي" ، الاتصالات الأسبستوس, Volume 3 (1960) رقم 5 صفحة 322.وقال انه يعطي اثنين من خوارزميات مختلفة هناك الأمثل الأرقام من المتوقع أن يكون "متفرق" (أي عدد صغير منها) واحد حالة العكس.
بعض الأسئلة المفتوحة:-
- إذا كان الرقم سالبا إذا ؟
- إذا كان الرقم 1024 ، ثم "تكرارا القسمة على 2" طريقة تكرار 10 مرات.
يمكننا تعديل algo لدعم الرقم السلبي على النحو التالي:-
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
والآن للتغلب على المشكلة الثانية يمكن أن نكتب algo مثل:-
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
من أجل استكمال المرجعية انظر :
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
private int get_bits_set(int v)
{
int c; // c accumulates the total bits set in v
for (c = 0; v>0; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c;
}
أعتقد براين هو كيرنيغان الطريقة سوف تكون مفيدة جدا...فإنه يذهب من خلال العديد من التكرار كما أن هناك مجموعة بت.حتى إذا كان لدينا كلمة 32-بت فقط مع ارتفاع قليلا ثم أنها سوف تذهب فقط مرة واحدة خلال الحلقة.
int countSetBits(unsigned int n) {
unsigned int n; // count the number of bits set in n
unsigned int c; // c accumulates the total bits set in n
for (c=0;n>0;n=n&(n-1)) c++;
return c;
}
نشرت في عام 1988 ، ج لغة البرمجة 2nd Ed.(بريان دبليوكيرنيغان ودينيس م.ريتشي) يذكر هذا في ممارسة الرياضة 2-9.في 19 نيسان / أبريل 2006 لا كانوث أشار لي أن هذا الأسلوب "نشرت لأول مرة من قبل بيتر Wegner في CACM 3 (عام 1960) ، 322.(اكتشف أيضا بشكل مستقل من قبل ديريك Lehmer ونشرت في عام 1964 في كتاب حرره Beckenbach.)"
يمكنني استخدام رمز أدناه والذي هو أكثر بديهية.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
المنطق :n & (n-1) تعيين آخر مجموعة بت ن.
P. S :أعرف أن هذا ليس O(1) حل ، وإن حل مثيرة للاهتمام.
ماذا يعني "أفضل خوارزمية"?قلل رمز أو صام الرمز ؟ التعليمات البرمجية الخاصة بك تبدو أنيقة جدا ولها ثابت وقت التنفيذ.رمز هو أيضا قصيرة جدا.
ولكن إذا كانت السرعة هي العامل الرئيسي وليس حجم التعليمات البرمجية ثم أعتقد أن اتبع يمكن أن يكون أسرع:
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
أعتقد أن هذا لن أكثر سرعة 64 بت القيمة ولكن 32 بت قيمة يمكن أن تكون أسرع.
كتبت بسرعة bitcount الكلي على RISC machines في عام 1990.أنها لا تستخدم المتقدمة الحسابية (الضرب ، القسمة،%), ذاكرة جلب (بطيء جدا) ، الفروع (بطيء جدا), ولكنها لا تتحمل وحدة المعالجة المركزية لديها 32 بت برميل شيفتر (وبعبارة أخرى ، > > 1 >> 32 تأخذ نفس الكمية من دورات.) فإنه يفترض أن الصغيرة الثوابت (مثل 6, 12, 24) لا تكلف شيئا لتحميل في السجلات ، أو يتم تخزينها في المؤقتات وإعادة استخدامها مرارا وتكرارا.
مع هذه الافتراضات ، التهم 32 بت في حوالي 16 دورة/الإرشادات التي تظهر على معظم RISC machines.علما أن 15 تعليمات/دورات بالقرب من الأدنى على عدد من الدورات أو تعليمات ، لأنه يبدو أن تأخذ ما لا يقل عن 3 تعليمات (قناع, التحول, مشغل) إلى قطع عدد من addends في نصف log_2(32) = 5 ، 5 × 3 = 15 تعليمات شبه lowerbound.
#define BitCount(X,Y) \
Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
Y = ((Y + (Y >> 3)) & 030707070707); \
Y = (Y + (Y >> 6)); \
Y = (Y + (Y >> 12) + (Y >> 24)) & 077;
هنا هو سر إلى الأكثر تعقيدا خطوة:
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
إذا كنت من العمود 1 (أ) أعلاه ، وتحول ذلك الحق 1 بت ، وطرح عليه من AB, أحصل على الناتج (CD).التمديد إلى 3 أجزاء مماثلة ؛ يمكنك التحقق من ذلك مع 8-صف منطقية الجدول مثل الألغام أعلاه إذا كنت ترغب في ذلك.
- لا جيليز
إذا كنت تستخدم C++ وثمة خيار آخر هو استخدام قالب metaprogramming:
// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
// return the least significant bit plus the result of calling ourselves with
// .. the shifted value
return (val & 0x1) + countBits<BITS-1>(val >> 1);
}
// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
return val & 0x1;
}
الاستخدام سيكون:
// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )
// another byte (this returns 7)
countBits<8>( 254 )
// counting bits in a word/short (this returns 1)
countBits<16>( 256 )
يمكنك بالطبع توسيع هذا القالب إلى استخدام أنواع مختلفة (حتى للكشف عن السيارات بت الحجم) ولكني ظللت بسيطة من أجل الوضوح.
تحرير:نسيت أن أذكر أن هذا أمر جيد لأنه يجب أن العمل في أي برنامج التحويل البرمجي C++ وهي في الأساس مجرد unrolls حلقة الخاص بك بالنسبة لك إذا كان قيمة ثابتة يتم استخدام بت عد (وبعبارة أخرى ، أنا متأكد إنها أسرع طريقة عامة ستجد)
أنا مولعا بشكل خاص من هذا المثال من ثروة الملف:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777)
- (((x)>>2)&0x33333333)
- (((x)>>3)&0x11111111))
أنا أحب ذلك أفضل لأنها جميلة جدا!
جافا JDK1.5
عدد صحيح.bitCount(ن) ؛
حيث n هو عدد الذين 1 هي أن تحصى.
تحقق أيضا ،
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}
لقد وجدت تنفيذ بت عد في صفيف باستخدام تعليمات SIMD (SSSE3 و AVX2).في 2-2.5 مرات أداء أفضل مما إذا كان سيتم استخدام __popcnt64 الجوهرية وظيفة.
SSSE3 الإصدار:
#include <smmintrin.h>
#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm128_setzero_si128();
for (size_t i = 0; i < size; i += 16)
{
//load 16-byte vector
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
//get low 4 bit for every byte in vector
__m128i lo = _mm_and_si128(_src, F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
}
uint64_t sum[2];
_mm_storeu_si128((__m128i*)sum, _sum);
return sum[0] + sum[1];
}
AVX2 الإصدار:
#include <immintrin.h>
#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
//load 32-byte vector
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
//get low 4 bit for every byte in vector
__m256i lo = _mm256_and_si256(_src, F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
}
uint64_t sum[4];
_mm256_storeu_si256((__m256i*)sum, _sum);
return sum[0] + sum[1] + sum[2] + sum[3];
}
أنا دائما استخدام هذا في تنافسية البرمجة وأنه من السهل أن أكتب وفعالة:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
هناك العديد من خوارزمية لحساب مجموعة بت ؛ ولكن أعتقد أن أفضل واحد هو أسرع واحد!يمكنك رؤية مفصلة في هذه الصفحة:
أقترح هذا واحد:
عد بت تعيين في 14 أو 24 أو 32 بت الكلمات باستخدام تعليمات 64-بت
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// option 2, for at most 24-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
// option 3, for at most 32-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
يتطلب هذا الأسلوب 64 بت وحدة المعالجة المركزية بسرعة معامل شعبة أن تكون فعالة.الخيار الأول يستغرق سوى 3 العمليات ؛ الخيار الثاني يأخذ 10;و الخيار الثالث يأخذ 15.
سريع C# الحل باستخدام المحسوبة مسبقا جدول بايت بت التهم مع المتفرعة على حجم المدخلات.
public static class BitCount
{
public static uint GetSetBitsCount(uint n)
{
var counts = BYTE_BIT_COUNTS;
return n <= 0xff ? counts[n]
: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
}
public static readonly uint[] BYTE_BIT_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
}
هنا محمول وحدة ( ANSI-C ) والتي يمكن أن المعيار كل من الخوارزميات على أي المعمارية.
وحدة المعالجة المركزية الخاصة بك لديها 9 بت بايت?لا مشكلة :-) في هذه اللحظة التي ينفذها 2 خوارزميات K&R خوارزمية بايت الحكمة جدول بحث.جدول البحث في المتوسط 3 مرات أسرع من K&R الخوارزمية.إذا كان شخص ما يمكن أن نجد طريقة لجعل "هاكر فرحة" خوارزمية المحمولة تتردد في إضافته في.
#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
32 بت أو لا ؟ أنا فقط جئت مع هذا الأسلوب في جاوة بعد القراءة "تكسير مقابلة الترميز"4th edition exercice 5.5 ( الفصل 5:بت التلاعب).إذا كان البت الأقل أهمية هو 1 الاضافة count, ثم الحق-تحويل عدد صحيح.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
وأعتقد أن هذا هو واحد أكثر سهولة من الحلول مع ثابت 0x33333333 بغض النظر عن مدى سرعة هم.هذا يعتمد على تعريف "أفضل خوارزمية" .
