وزن هامينغ

وزن هامينغ لسلسلة هو عدد الرموز المختلفة عن رمز الصفر في الأبجدية المستخدمة. وهو بالتالي يُعادل مسافة هامينغ من سلسلة جميع رموزها أصفار ولها نفس الطول. في الحالة الأكثر شيوعًا، أي مجموعة معينة من البتات ، يُمثل هذا الوزن عدد البتات التي قيمتها 1، أو مجموع أرقام التمثيل الثنائي لعدد معين ومعيار ℓ₁ لمتجه بت. في هذه الحالة الثنائية، يُطلق عليه أيضًا اسم عدد البتات ، ^{[ 1 ]} أو مجموع البتات ، أو المجموع الجانبي ، ^{[ 2 ]} أو مجموع البتات . ^{[ 3 ]}

سُمّي وزن هامينغ نسبةً إلى عالم الرياضيات الأمريكي ريتشارد هامينغ ، مع أنه لم يكن صاحب الفكرة. ^{[ 5 ]} وقد استُخدم وزن هامينغ للأعداد الثنائية عام 1899 من قِبل جيمس دبليو إل غليشر لإعطاء صيغة لعدد معاملات ذات الحدين الفردية في صف واحد من مثلث باسكال . ^{[ 6 ]} وقدّم إيرفينغ إس ريد مفهومًا مُكافئًا لوزن هامينغ في الحالة الثنائية عام 1954. ^{[ 7 ]}

يُستخدم وزن هامينغ في العديد من المجالات، بما في ذلك نظرية المعلومات ، ونظرية الترميز ، وعلم التشفير . ومن أمثلة تطبيقات وزن هامينغ ما يلي:

• في عملية الرفع الأسي المعياري بالتربيع ، يكون عدد عمليات الضرب المعياري اللازمة للأس e هو log₂e ₊ weight( e ) . لهذا السبب، يُختار عادةً قيمة المفتاح العام e المستخدمة في RSA لتكون ذات وزن هامينغ منخفض. ^{[ 8 ]}
• يحدد وزن هامينغ أطوال المسارات بين العقد في جداول التجزئة الموزعة Chord . ^{[ 9 ]}
• يتم عادةً تنفيذ عمليات البحث عن رمز قزحية العين في قواعد البيانات البيومترية عن طريق حساب مسافة هامينغ لكل سجل مخزن. ^{[ 10 ]}
• في برامج الشطرنج الحاسوبية التي تستخدم تمثيل لوحة البت ، يُعطي وزن هامينغ للوحة البت عدد القطع المتبقية من نوع معين في اللعبة، أو عدد مربعات اللوحة التي تسيطر عليها قطع أحد اللاعبين، وبالتالي فهو عامل مهم يساهم في قيمة الموقف. ^{[ 11 ]}
• يمكن استخدام وزن هامينغ لحساب إيجاد المجموعة الأولى بكفاءة باستخدام المتطابقة ffs(x) = pop(x ^ (x - 1)). يُعد هذا مفيدًا على منصات مثل SPARC التي تحتوي على تعليمات وزن هامينغ مدمجة ولكنها لا تحتوي على تعليمات إيجاد المجموعة الأولى مدمجة. ^{[ 12 ] [ 1 ]}
• يمكن تفسير عملية وزن هامينغ على أنها تحويل من نظام الأرقام الأحادية إلى الأرقام الثنائية . ^{[ 13 ]}

يُعدّ عدد البتات في سلسلة البتات ضروريًا في علم التشفير وتطبيقات أخرى. ويمكن حساب مسافة هامينغ بين كلمتين A و B من خلال وزن هامينغ لعملية XOR بين A ^و B. ^{[ 1} ]

لقد حظيت مشكلة كيفية تنفيذها بكفاءة باهتمام واسع في الدراسات. تتوفر عملية حسابية واحدة، أو عمليات متوازية على متجهات البتات، في بعض المعالجات . أما بالنسبة للمعالجات التي تفتقر إلى هذه الميزات، فإن أفضل الحلول المعروفة تعتمد على جمع القيم في نمط شجري. على سبيل المثال، لحساب عدد البتات التي قيمتها 1 في العدد الثنائي ذي 16 بت a  =  0110  1100  1011  1010، يمكن إجراء العمليات التالية:

هنا، تُجرى العمليات كما في لغة البرمجة C ، حيث X >> Yتعني `x` إزاحة X إلى اليمين بمقدار Y بت، و`x & Y` تعني عملية AND المنطقية بين X وY، و`+` تعني الجمع العادي. تعتمد أفضل الخوارزميات المعروفة لحل هذه المشكلة على المفهوم الموضح أعلاه، وهي مُدرجة هنا: ^{[ 1 ]}

// أنواع البيانات والثوابت المستخدمة في الدوال أدناه // uint64_t هو نوع متغير عدد صحيح غير مُوقّع 64 بت (مُعرّف في إصدار C99 من لغة C) const uint64_t m1 = 0x55555555555555555 ; // ثنائي: 0101... const uint64_t m2 = 0x33333333333333333 ; // ثنائي: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f ; // ثنائي: 4 أصفار، 4 آحاد ... const uint64_t m8 = 0x00ff00ff00ff00ff ; // ثنائي: 8 أصفار، 8 آحاد ... const uint64_t m16 = 0x0000ffff0000ffff ; // ثنائي: 16 صفرًا، 16 آحاد ... const uint64_t m32 = 0x00000000ffffffff ; // ثنائي: 32 صفرًا، 32 آحاد const uint64_t h01 = 0x0101010101010101 ; // مجموع 256 مرفوعًا للأس 0، 1، 2، 3 ...// هذا تطبيق بسيط، معروض للمقارنة، // وللمساعدة في فهم الدوال الأفضل. // تستخدم هذه الخوارزمية 24 عملية حسابية (الإزاحة، والجمع، و AND). int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); // ضع عدد كل 2 بت في هذين البتّين x = ( x & m2 ) + (( x >> 2 ) & m2 ); // ضع عدد كل 4 بت في هذه البتّات الأربعة x = ( x & m4 ) + (( x >> 4 ) & m4 ); // ضع عدد كل 8 بت في هذه البتّات الثمانية x = ( x & m8 ) + (( x >> 8 ) & m8 ); // ضع عدد كل 16 بت في هذه البتّات الستة عشر x = ( x & m16 ) + (( x >> 16 ) & m16 ); // ضع عدد كل 32 بت في تلك الـ 32 بت x = ( x & m32 ) + (( x >> 32 ) & m32 ); // ضع عدد كل 64 بت في تلك الـ 64 بت return x ; }// يستخدم هذا عددًا أقل من العمليات الحسابية مقارنةً بأي تطبيق آخر معروف // على الأجهزة ذات الضرب البطيء. // تستخدم هذه الخوارزمية 17 عملية حسابية. int popcount64b ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; // ضع عدد كل 2 بت في هذين البتّين x = ( x & m2 ) + (( x >> 2 ) & m2 ); // ضع عدد كل 4 بت في هذه البتّات x = ( x + ( x >> 4 )) & m4 ; // ضع عدد كل 8 بت في هذه البتّات x += x >> 8 ; // ضع عدد كل 16 بت في أدنى 8 بتّ x += x >> 16 ; // ضع عدد كل 32 بت في أدنى 8 بتّ x += x >> 32 ; // ضع عدد كل 64 بت في أدنى 8 بتّ return x & 0x7f ; }// يستخدم هذا عددًا أقل من العمليات الحسابية مقارنةً بأي تطبيق آخر معروف // على الأجهزة ذات الضرب السريع. // تستخدم هذه الخوارزمية 12 عملية حسابية، إحداها عملية ضرب. int popcount64c ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; // ضع عدد كل 2 بت في هذين البتّين x = ( x & m2 ) + (( x >> 2 ) & m2 ); // ضع عدد كل 4 بت في هذه البتّات x = ( x + ( x >> 4 )) & m4 ; // ضع عدد كل 8 بت في هذه البتّات return ( x * h01 ) >> 56 ; // تُرجع البتّات الثمانية المتبقية من x + (x<<8) + (x<<16) + (x<<24) + ... }

تتميز التطبيقات المذكورة أعلاه بأفضل أداء في أسوأ الحالات مقارنةً بأي خوارزمية معروفة. مع ذلك، عندما يُتوقع أن تحتوي قيمة ما على عدد قليل من البتات غير الصفرية، قد يكون من الأجدى استخدام خوارزميات تحسب هذه البتات بتًا بتًا. وكما وصف ويغنر في عام 1960 ^{[ 14 ]،} فإن عملية AND المنطقية للبتات بين x و x - 1 تختلف عن x فقط في تصفير البت الأقل أهمية غير الصفري: طرح 1 يُحوّل سلسلة الأصفار الموجودة في أقصى اليمين إلى 1، ويُحوّل البت 1 الموجود في أقصى اليمين إلى 0. إذا كانت x تحتوي في الأصل على n بتًا قيمتها 1، فبعد n تكرارًا فقط لهذه العملية، ستُختزل x إلى الصفر. يعتمد التطبيق التالي على هذا المبدأ.  

// يكون هذا أفضل عندما تكون معظم البتات في x تساوي صفرًا. // تعمل هذه الخوارزمية بنفس الطريقة لجميع أحجام البيانات. // تستخدم هذه الخوارزمية 3 عمليات حسابية ومقارنة/تفرع واحد لكل بت "1" في x. int popcount64d ( uint64_t x ) { int count ; for ( count = 0 ; x ; count ++ ) x &= x - 1 ; return count ; }

ومن الأمور الجديرة بالاهتمام هنا العلاقة الوثيقة بين Popcount و FFS و CLZ.

إذا سُمح باستخدام ذاكرة أكبر، يُمكننا حساب وزن هامينغ بشكل أسرع من الطرق المذكورة أعلاه. مع ذاكرة غير محدودة، يُمكننا ببساطة إنشاء جدول بحث كبير لوزن هامينغ لكل عدد صحيح 64 بت. إذا أمكننا تخزين جدول بحث لدالة هامينغ لكل عدد صحيح 16 بت، يُمكننا القيام بما يلي لحساب وزن هامينغ لكل عدد صحيح 32 بت.

static uint8_t wordbits [ 65536 ] = { /* عدد بتات الأعداد الصحيحة من 0 إلى 65535، شاملةً */ }; // تستخدم هذه الخوارزمية 3 عمليات حسابية وقراءتين من الذاكرة. int popcount32e ( uint32_t x ) { return wordbits [ x & 0xFFFF ] + wordbits [ x >> 16 ]; }

// اختياريًا، يمكن ملء جدول wordbits[] باستخدام هذه الدالة int popcount32e_init ( void ) { uint32_t i ; uint16_t x ; int count ; for ( i = 0 ; i <= 0xFFFF ; i ++ ) { x = i ; for ( count = 0 ; x ; count ++ ) // مستعارة من popcount64d() أعلاه x &= x - 1 ; wordbits [ i ] = count ; } }

تم تقديم خوارزمية تكرارية في دونوفان وكيرنيغان ^{[ 15 ]}

/* يمكن أن يختلف وزن i عن وزن i / 2 فقط في أقل بت أهمية من i */ int popcount32e_init ( void ) { int i ; for ( i = 1 ; sizeof wordbits / sizeof * wordbits > i ; ++ i ) wordbits [ i ] = wordbits [ i >> 1 ] + ( 1 & i ); }

أظهر Muła et al. ^{[ 16 ]} أن النسخة المتجهة من popcount64b يمكن أن تعمل بشكل أسرع من التعليمات المخصصة (على سبيل المثال، popcnt على معالجات x64).

تُعد خوارزمية هارلي-سيل ^{[ 17 ]} واحدة من أسرع الخوارزميات التي لا تتطلب سوى عمليات حسابية على الأعداد الصحيحة. ^{[ 18 ]}

في ترميز تصحيح الأخطاء ، يُعرف الحد الأدنى لوزن هامينغ، والذي يُشار إليه عادةً بالوزن الأدنى w_{_min} للرمز، بأنه وزن أقل كلمة رمزية غير صفرية وزنًا. وزن w لكلمة رمزية هو عدد الآحاد (1) فيها. على سبيل المثال، وزن الكلمة 11001010 هو 4.

في رمز الكتلة الخطي، يمثل الوزن الأدنى أيضًا مسافة هامينغ الدنيا ( d _min )، ويحدد قدرة الرمز على تصحيح الأخطاء. إذا كان w _min  = n ، فإن d _min = n، وسيصحح الرمز ما يصل إلى d _min /2 من الأخطاء. ^{[ 19 ]}   

تُوفّر بعض مُجمّعات لغة C دوالًا مُضمّنة تُتيح إمكانية عدّ البتات. على سبيل المثال، يتضمن مُجمّع GCC (منذ الإصدار 3.4 في أبريل 2004) دالةً مُدمجةً __builtin_popcountتستخدم تعليمة المعالج إن وُجدت، أو تُنفّذها باستخدام مكتبة فعّالة في حال عدم توفّرها. ^{[ 20 ]} وقد أضاف مُجمّع LLVM-GCC هذه الدالة منذ الإصدار 1.5 في يونيو 2005. ^{[ 21 ]}

في مكتبة C++ القياسيةbitset ، تحتوي بنية بيانات مصفوفة البتات count()على دالة لحساب عدد البتات المُفعّلة. في C++20<bit> ، أُضيف ملف رأس جديد يحتوي على std::popcountدالتين std::has_single_bitتأخذان وسائط من نوع عدد صحيح غير مُوقّع.

BitSetفي لغة جافا، تحتوي بنية بيانات مصفوفة البتات القابلة للتوسيع على BitSet.cardinality()دالة لحساب عدد البتات المُفعّلة. بالإضافة إلى ذلك، توجد Integer.bitCount(int)دالتان Long.bitCount(long)لحساب البتات في الأعداد الصحيحة الأولية ذات 32 بت و64 بت على التوالي. BigIntegerكما تحتوي فئة الأعداد الصحيحة ذات الدقة العشوائية على BigInteger.bitCount()دالة لحساب البتات.

في لغة بايثون ، intيحتوي النوع على bit_count()دالة لحساب عدد البتات المُفعّلة. أُضيفت هذه الخاصية في بايثون 3.10، التي صدرت في أكتوبر 2021. ^{[ 22 ]}

في لغة Common Lisp ، تُعيد الدالة logcount، عند إعطائها عددًا صحيحًا غير سالب، عدد البتات التي قيمتها 1. (أما بالنسبة للأعداد الصحيحة السالبة، فتعيد عدد البتات التي قيمتها 0 في تمثيل المتمم الثنائي). في كلتا الحالتين، يمكن أن يكون العدد الصحيح عددًا كبيرًا .

ابتداءً من GHC 7.4، تحتوي حزمة Haskell الأساسية على popCountدالة متاحة لجميع الأنواع التي هي نسخ من Bitsالفئة (المتاحة من Data.Bitsالوحدة النمطية). ^{[ 23 ]}

توفر نسخة MySQL من لغة SQLBIT_COUNT() وظيفة قياسية. ^{[ 24 ]}

تحتوي لغة فورتران 2008 على الدالة الأساسية القياسية popcntالتي تُرجع عدد البتات غير الصفرية داخل عدد صحيح (أو مصفوفة أعداد صحيحة). ^{[ 25 ]}

تحتوي بعض الآلات الحاسبة العلمية القابلة للبرمجة على أوامر خاصة لحساب عدد البتات المُفعّلة، على سبيل المثال #Bفي HP-16C . ^{[ 3 ]}

تُنفذ FreePascal دالة popcnt منذ الإصدار 3.0. ^{[ 26 ]}

• قام حاسوب IBM STRETCH في الستينيات بحساب عدد البتات المُفعّلة بالإضافة إلى عدد الأصفار البادئة كناتج ثانوي لجميع العمليات المنطقية. ^{[ 1 ]}
• تضمنت أجهزة الكمبيوتر العملاقة من نوع كراي في بداياتها تعليمات برمجية لحساب عدد السكان، ويُشاع أن وكالة الأمن القومي التابعة للحكومة الأمريكية قد طلبتها تحديدًا لتطبيقات تحليل الشفرات . ^{[ 1 ]}
• تضمنت أجهزة سلسلة 6000 و Cyber ​​70/170 التابعة لشركة Control Data Corporation (CDC) تعليمات عد السكان؛ في COMPASS ، تم ترميز هذه التعليمات على النحو التالي CXi.
• تُعرّف بنية SPARC الإصدار 9 ذات 64 بت POPCتعليمة معينة، ^{[ 12 ] [ 1 ]} ولكن معظم التطبيقات لا تُنفذها، مما يتطلب محاكاتها بواسطة نظام التشغيل. ^{[ 27 ]}
• يحتوي نموذج الكمبيوتر MMIX الخاص بدونالد كنوث ، والذي سيحل محل MIX في كتابه "فن برمجة الكمبيوتر"، على SADDتعليمة منذ عام 1999. SADD a,b,cيقوم هذا النموذج بحساب جميع البتات التي تساوي 1 في b و 0 في c ويكتب النتيجة إلى a.
• كان معالج Compaq 's Alpha 21264A ، الذي تم إصداره في عام 1999، أول تصميم لوحدة المعالجة المركزية من سلسلة Alpha يحتوي على امتداد العد ( CIX).
• تتميز معالجات Blackfin من Analog DevicesONES بتعليمات لإجراء عملية عد السكان 32 بت. ^{[ 28 ]}
• قدمت بنية برشلونة من AMD مجموعة تعليمات معالجة البتات المتقدمة (ABM) POPCNTكجزء من امتدادات SSE4a في عام 2007.
• قدمت معالجات Intel CorePOPCNT تعليمات مع امتداد مجموعة تعليمات SSE4.2 ، والتي كانت متاحة لأول مرة في معالج Core i7 القائم على Nehalem ، والذي تم إصداره في نوفمبر 2008.
• أدخلت بنية ARMVCNT التعليمات كجزء من امتدادات SIMD المتقدمة ( NEON ).
• أدخلت بنية RISC-V هذه التعليمات كجزءCPOP من امتداد معالجة البتات (B). ^{[ 29 ]}

• متمم الاثنين
• انتشروا

• شرويبل، ريتشارد سي .؛ أورمان، هيلاري ك. (29 فبراير 1972). "تجميع". هاكم . بقلم بيلر، مايكل؛ جوسبر، رالف ويليام ؛ شرويبل، ريتشارد سي. (تقرير). مختبر الذكاء الاصطناعي ، معهد ماساتشوستس للتكنولوجيا ، كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية. مذكرة معهد ماساتشوستس للتكنولوجيا للذكاء الاصطناعي رقم 239.( البند 169 : كود تجميع عد السكان لجهاز PDP/6-10.)

• خوارزميات التجميع السحرية . شرح لخوارزميات عدّ السكان المُحسّنة وغيرها من الخوارزميات مع نماذج برمجية.
• حيل التلاعب بالبتات: عدة خوارزميات مع شفرة لحساب البتات المُفعّلة.
• ضروري وكافٍ مؤرشف في 2017-09-23 على Wayback Machine - بواسطة داميان وينتور - يحتوي على كود بلغة C# لتطبيقات وزن هامينغ المختلفة.
• ما هي أفضل خوارزمية لحساب عدد البتات المُفعّلة في عدد صحيح 32 بت؟ - Stackoverflow