हैमिंग वेट

From Vigyanwiki
Revision as of 17:01, 25 July 2023 by Manidh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

स्ट्रिंग का हैमिंग वेट (कंप्यूटर विज्ञान) उन प्रतीकों की संख्या है जो प्रयुक्त वर्णमाला के शून्य-प्रतीक से भिन्न होते हैं। इस प्रकार यह समान लंबाई की पूर्ण-शून्य स्ट्रिंग से हैमिंग दूरी के सामान्य है। सबसे विशिष्ट स्थिति के लिए, अंश की स्ट्रिंग, यह स्ट्रिंग में 1 की संख्या है, या किसी दिए गए नंबर की बाइनरी अंक प्रणाली का अंक योग और टैक्सीकैब ज्यामिति या ℓ₁ बिट सदिश का मानदंड इस द्विआधारी स्थिति में, इसे जनसंख्या गणना भी कहा जाता है,[1] पॉपकाउंट, पार्श्व में योग,[2] या बिट योग का उपयोग किया जाता है.[3]

Examples
String Hamming weight
11101 4
11101000 4
00000000 0
678012340567 10
<graph>{"legends":[],"scales":[{"type":"linear","name":"x","zero":false,"domain":{"data":"chart","field":"x"},"range":"width","nice":true},{"type":"linear","name":"y","domain":{"data":"chart","field":"y"},"zero":false,"range":"height","nice":true},{"domain":{"data":"chart","field":"series"},"type":"ordinal","name":"color","range":["red"]}],"version":2,"marks":[{"type":"line","properties":{"hover":{"stroke":{"value":"red"}},"update":{"stroke":{"scale":"color","field":"series"}},"enter":{"y":{"scale":"y","field":"y"},"x":{"scale":"x","field":"x"},"stroke":{"scale":"color","field":"series"},"strokeWidth":{"value":1}}},"from":{"data":"chart"}}],"height":200,"axes":[{"type":"x","scale":"x","format":"d","properties":{"title":{"fill":{"value":"#54595d"}},"grid":{"stroke":{"value":"#54595d"}},"ticks":{"stroke":{"value":"#54595d"}},"axis":{"strokeWidth":{"value":2},"stroke":{"value":"#54595d"}},"labels":{"fill":{"value":"#54595d"}}},"grid":false},{"type":"y","scale":"y","format":"d","properties":{"title":{"fill":{"value":"#54595d"}},"grid":{"stroke":{"value":"#54595d"}},"ticks":{"stroke":{"value":"#54595d"}},"axis":{"strokeWidth":{"value":2},"stroke":{"value":"#54595d"}},"labels":{"fill":{"value":"#54595d"}}},"grid":true}],"data":[{"format":{"parse":{"y":"integer","x":"integer"},"type":"json"},"name":"chart","values":[{"y":0,"series":"y","x":0},{"y":1,"series":"y","x":1},{"y":1,"series":"y","x":2},{"y":2,"series":"y","x":3},{"y":1,"series":"y","x":4},{"y":2,"series":"y","x":5},{"y":2,"series":"y","x":6},{"y":3,"series":"y","x":7},{"y":1,"series":"y","x":8},{"y":2,"series":"y","x":9},{"y":2,"series":"y","x":10},{"y":3,"series":"y","x":11},{"y":2,"series":"y","x":12},{"y":3,"series":"y","x":13},{"y":3,"series":"y","x":14},{"y":4,"series":"y","x":15},{"y":1,"series":"y","x":16},{"y":2,"series":"y","x":17},{"y":2,"series":"y","x":18},{"y":3,"series":"y","x":19},{"y":2,"series":"y","x":20},{"y":3,"series":"y","x":21},{"y":3,"series":"y","x":22},{"y":4,"series":"y","x":23},{"y":2,"series":"y","x":24},{"y":3,"series":"y","x":25},{"y":3,"series":"y","x":26},{"y":4,"series":"y","x":27},{"y":3,"series":"y","x":28},{"y":4,"series":"y","x":29},{"y":4,"series":"y","x":30},{"y":5,"series":"y","x":31},{"y":1,"series":"y","x":32},{"y":2,"series":"y","x":33},{"y":2,"series":"y","x":34},{"y":3,"series":"y","x":35},{"y":2,"series":"y","x":36},{"y":3,"series":"y","x":37},{"y":3,"series":"y","x":38},{"y":4,"series":"y","x":39},{"y":2,"series":"y","x":40},{"y":3,"series":"y","x":41},{"y":3,"series":"y","x":42},{"y":4,"series":"y","x":43},{"y":3,"series":"y","x":44},{"y":4,"series":"y","x":45},{"y":4,"series":"y","x":46},{"y":5,"series":"y","x":47},{"y":2,"series":"y","x":48},{"y":3,"series":"y","x":49},{"y":3,"series":"y","x":50},{"y":4,"series":"y","x":51},{"y":3,"series":"y","x":52},{"y":4,"series":"y","x":53},{"y":4,"series":"y","x":54},{"y":5,"series":"y","x":55},{"y":3,"series":"y","x":56},{"y":4,"series":"y","x":57},{"y":4,"series":"y","x":58},{"y":5,"series":"y","x":59},{"y":4,"series":"y","x":60},{"y":5,"series":"y","x":61},{"y":5,"series":"y","x":62},{"y":6,"series":"y","x":63},{"y":1,"series":"y","x":64},{"y":2,"series":"y","x":65},{"y":2,"series":"y","x":66},{"y":3,"series":"y","x":67},{"y":2,"series":"y","x":68},{"y":3,"series":"y","x":69},{"y":3,"series":"y","x":70},{"y":4,"series":"y","x":71},{"y":2,"series":"y","x":72},{"y":3,"series":"y","x":73},{"y":3,"series":"y","x":74},{"y":4,"series":"y","x":75},{"y":3,"series":"y","x":76},{"y":4,"series":"y","x":77},{"y":4,"series":"y","x":78},{"y":5,"series":"y","x":79},{"y":2,"series":"y","x":80},{"y":3,"series":"y","x":81},{"y":3,"series":"y","x":82},{"y":4,"series":"y","x":83},{"y":3,"series":"y","x":84},{"y":4,"series":"y","x":85},{"y":4,"series":"y","x":86},{"y":5,"series":"y","x":87},{"y":3,"series":"y","x":88},{"y":4,"series":"y","x":89},{"y":4,"series":"y","x":90},{"y":5,"series":"y","x":91},{"y":4,"series":"y","x":92},{"y":5,"series":"y","x":93},{"y":5,"series":"y","x":94},{"y":6,"series":"y","x":95},{"y":2,"series":"y","x":96},{"y":3,"series":"y","x":97},{"y":3,"series":"y","x":98},{"y":4,"series":"y","x":99},{"y":3,"series":"y","x":100},{"y":4,"series":"y","x":101},{"y":4,"series":"y","x":102},{"y":5,"series":"y","x":103},{"y":3,"series":"y","x":104},{"y":4,"series":"y","x":105},{"y":4,"series":"y","x":106},{"y":5,"series":"y","x":107},{"y":4,"series":"y","x":108},{"y":5,"series":"y","x":109},{"y":5,"series":"y","x":110},{"y":6,"series":"y","x":111},{"y":3,"series":"y","x":112},{"y":4,"series":"y","x":113},{"y":4,"series":"y","x":114},{"y":5,"series":"y","x":115},{"y":4,"series":"y","x":116},{"y":5,"series":"y","x":117},{"y":5,"series":"y","x":118},{"y":6,"series":"y","x":119},{"y":4,"series":"y","x":120},{"y":5,"series":"y","x":121},{"y":5,"series":"y","x":122},{"y":6,"series":"y","x":123},{"y":5,"series":"y","x":124},{"y":6,"series":"y","x":125},{"y":6,"series":"y","x":126},{"y":7,"series":"y","x":127},{"y":1,"series":"y","x":128},{"y":2,"series":"y","x":129},{"y":2,"series":"y","x":130},{"y":3,"series":"y","x":131},{"y":2,"series":"y","x":132},{"y":3,"series":"y","x":133},{"y":3,"series":"y","x":134},{"y":4,"series":"y","x":135},{"y":2,"series":"y","x":136},{"y":3,"series":"y","x":137},{"y":3,"series":"y","x":138},{"y":4,"series":"y","x":139},{"y":3,"series":"y","x":140},{"y":4,"series":"y","x":141},{"y":4,"series":"y","x":142},{"y":5,"series":"y","x":143},{"y":2,"series":"y","x":144},{"y":3,"series":"y","x":145},{"y":3,"series":"y","x":146},{"y":4,"series":"y","x":147},{"y":3,"series":"y","x":148},{"y":4,"series":"y","x":149},{"y":4,"series":"y","x":150},{"y":5,"series":"y","x":151},{"y":3,"series":"y","x":152},{"y":4,"series":"y","x":153},{"y":4,"series":"y","x":154},{"y":5,"series":"y","x":155},{"y":4,"series":"y","x":156},{"y":5,"series":"y","x":157},{"y":5,"series":"y","x":158},{"y":6,"series":"y","x":159},{"y":2,"series":"y","x":160},{"y":3,"series":"y","x":161},{"y":3,"series":"y","x":162},{"y":4,"series":"y","x":163},{"y":3,"series":"y","x":164},{"y":4,"series":"y","x":165},{"y":4,"series":"y","x":166},{"y":5,"series":"y","x":167},{"y":3,"series":"y","x":168},{"y":4,"series":"y","x":169},{"y":4,"series":"y","x":170},{"y":5,"series":"y","x":171},{"y":4,"series":"y","x":172},{"y":5,"series":"y","x":173},{"y":5,"series":"y","x":174},{"y":6,"series":"y","x":175},{"y":3,"series":"y","x":176},{"y":4,"series":"y","x":177},{"y":4,"series":"y","x":178},{"y":5,"series":"y","x":179},{"y":4,"series":"y","x":180},{"y":5,"series":"y","x":181},{"y":5,"series":"y","x":182},{"y":6,"series":"y","x":183},{"y":4,"series":"y","x":184},{"y":5,"series":"y","x":185},{"y":5,"series":"y","x":186},{"y":6,"series":"y","x":187},{"y":5,"series":"y","x":188},{"y":6,"series":"y","x":189},{"y":6,"series":"y","x":190},{"y":7,"series":"y","x":191},{"y":2,"series":"y","x":192},{"y":3,"series":"y","x":193},{"y":3,"series":"y","x":194},{"y":4,"series":"y","x":195},{"y":3,"series":"y","x":196},{"y":4,"series":"y","x":197},{"y":4,"series":"y","x":198},{"y":5,"series":"y","x":199},{"y":3,"series":"y","x":200},{"y":4,"series":"y","x":201},{"y":4,"series":"y","x":202},{"y":5,"series":"y","x":203},{"y":4,"series":"y","x":204},{"y":5,"series":"y","x":205},{"y":5,"series":"y","x":206},{"y":6,"series":"y","x":207},{"y":3,"series":"y","x":208},{"y":4,"series":"y","x":209},{"y":4,"series":"y","x":210},{"y":5,"series":"y","x":211},{"y":4,"series":"y","x":212},{"y":5,"series":"y","x":213},{"y":5,"series":"y","x":214},{"y":6,"series":"y","x":215},{"y":4,"series":"y","x":216},{"y":5,"series":"y","x":217},{"y":5,"series":"y","x":218},{"y":6,"series":"y","x":219},{"y":5,"series":"y","x":220},{"y":6,"series":"y","x":221},{"y":6,"series":"y","x":222},{"y":7,"series":"y","x":223},{"y":3,"series":"y","x":224},{"y":4,"series":"y","x":225},{"y":4,"series":"y","x":226},{"y":5,"series":"y","x":227},{"y":4,"series":"y","x":228},{"y":5,"series":"y","x":229},{"y":5,"series":"y","x":230},{"y":6,"series":"y","x":231},{"y":4,"series":"y","x":232},{"y":5,"series":"y","x":233},{"y":5,"series":"y","x":234},{"y":6,"series":"y","x":235},{"y":5,"series":"y","x":236},{"y":6,"series":"y","x":237},{"y":6,"series":"y","x":238},{"y":7,"series":"y","x":239},{"y":4,"series":"y","x":240},{"y":5,"series":"y","x":241},{"y":5,"series":"y","x":242},{"y":6,"series":"y","x":243},{"y":5,"series":"y","x":244},{"y":6,"series":"y","x":245},{"y":6,"series":"y","x":246},{"y":7,"series":"y","x":247},{"y":5,"series":"y","x":248},{"y":6,"series":"y","x":249},{"y":6,"series":"y","x":250},{"y":7,"series":"y","x":251},{"y":6,"series":"y","x":252},{"y":7,"series":"y","x":253},{"y":7,"series":"y","x":254},{"y":8,"series":"y","x":255},{"y":1,"series":"y","x":256}]}],"width":300}</graph>
A plot for the population count (Hamming weight for binary numbers) for (decimal) numbers 0 to 256.[4][5][6]


इतिहास और उपयोग

हैमिंग वेट का नाम रिचर्ड हैमिंग के नाम पर रखा गया है, चूँकि उन्होंने इस धारणा की उत्पत्ति नहीं की थी।[7] बाइनरी संख्याओं के हैमिंग वेट का उपयोग 1899 में जेम्स व्हिटब्रेड ली ग्लैशर द्वारा पास्कल के त्रिकोण की पंक्ति में गोल्ड के अनुक्रम के लिए सूत्र देने के लिए किया गया था।[8] इरविंग एस. रीड ने 1954 में बाइनरी स्थिति में हैमिंग वेट के सामान्य अवधारणा प्रस्तुत की थी।[9]

हैमिंग वेट का उपयोग सूचना सिद्धांत, कोडिंग सिद्धांत और क्रिप्टोग्राफी सहित कई विषयों में किया जाता है। हैमिंग वज़न के अनुप्रयोगों के उदाहरणों में सम्मिलित हैं:

  • वर्ग द्वारा मॉड्यूलर घातांक में, घातांक e के लिए आवश्यक मॉड्यूलर गुणन की संख्या लॉग है यही कारण है कि आरएसए (एल्गोरिदम) में प्रयुक्त सार्वेटिक कीज मान e को सामान्यतः कम हैमिंग वेट की संख्या के रूप में चुना जाता है।[10]
  • हैमिंग वेट कॉर्ड (वितरित हैश तालिका) में नोड्स के बीच पथ की लंबाई निर्धारित करता है।[11]
  • बायोमेट्रिक डेटाबेस में आईरिसकोड लुकअप सामान्यतः प्रत्येक संग्रहीत रिकॉर्ड के लिए हैमिंग दूरी की गणना करके कार्यान्वित किया जाता है।
  • बिटबोर्ड प्रतिनिधित्व का उपयोग करने वाले कंप्यूटर चेस प्रोग्राम में, बिटबोर्ड का हैमिंग वेट खेल में शेष दिए गए प्रकार के टुकड़ों की संख्या, या खिलाड़ी के टुकड़ों द्वारा नियंत्रित बोर्ड के वर्गों की संख्या देता है, और इसलिए यह महत्वपूर्ण योगदान है किसी पद के मूल्य के लिए शब्द का उपयोग किया जाता है।
  • हैमिंग वेट का उपयोग पहचान एफएफएस ffs(x) = pop(x ^ (x - 1)) का उपयोग करके पहले सेट को कुशलतापूर्वक खोजने के लिए किया जा सकता है। यह स्पार्क जैसे प्लेटफ़ॉर्म पर उपयोगी है जिसमें हार्डवेयर हैमिंग वेट निर्देश हैं किन्तु कोई हार्डवेयर पहले सेट निर्देश नहीं खोजता है।[12][1]
  • हैमिंग वेट ऑपरेशन की व्याख्या यूनरी अंक प्रणाली से बाइनरी संख्याओं में रूपांतरण के रूप में की जा सकती है।[13]
  • बिट सरणी और तरंगिका वृक्ष जैसी कुछ संक्षिप्त डेटा संरचनाओं के कार्यान्वयन में किया जाता है।

कुशल कार्यान्वयन

क्रिप्टोग्राफी और अन्य अनुप्रयोगों में बिट सरणी की जनसंख्या गणना की अधिकांशतः आवश्यकता होती है। दो शब्दों a और b की हैमिंग दूरी की गणना a एक्स या b के हैमिंग वेट के रूप में की जा सकती है।[1]

इसे कुशलतापूर्वक कैसे कार्यान्वित किया जाए इसकी समस्या का व्यापक अध्ययन किया गया है। इस प्रकार गणना के लिए एकल ऑपरेशन, या बिट वैक्टर पर समानांतर संचालन प्रोसेसर समर्थन हैं। जिन प्रोसेसरों में उन सुविधाओं की कमी है, उनके लिए ज्ञात सर्वोत्तम समाधान ट्री पैटर्न में गिनती जोड़ने पर आधारित हैं। उदाहरण के लिए, 16-बिट बाइनरी संख्या a = 0110 1100 1011 1010 में 1 बिट की संख्या गिनने के लिए, ये ऑपरेशन किए जा सकते हैं:

अभिव्यक्ति बाइनरी दशमलव टिप्पणी
a 01 10 11 00 10 11 10 10 27834 मूल क्रमांक
b0 = (a >> 0) & 01 01 01 01 01 01 01 01 01 00 01 00 00 01 00 00 1, 0, 1, 0, 0, 1, 0, 0 a से प्रत्येक अन्य बिट
b1 = (a >> 1) & 01 01 01 01 01 01 01 01 00 01 01 00 01 01 01 01 0, 1, 1, 0, 1, 1, 1, 1 a से शेष बिट्स
c = b0 + b1 01 01 10 00 01 10 01 01 1, 1, 2, 0, 1, 2, 1, 1 प्रत्येक 2-बिट स्लाइस में 1s की गिनती
d0 = (c >> 0) & 0011 0011 0011 0011 0001 0000 0010 0001 1, 0, 2, 1 सी से हर दूसरी गिनती
d2 = (c >> 2) & 0011 0011 0011 0011 0001 0010 0001 0001 1, 2, 1, 1 शेष की गणना c से की जाती है
e = d0 + d2 0010 0010 0011 0010 2, 2, 3, 2 a के प्रत्येक 4-बिट स्लाइस में 1s की गिनती
f0 = (e >> 0) & 00001111 00001111 00000010 00000010 2, 2 e से प्रत्येक अन्य गिनती
f4 = (e >> 4) & 00001111 00001111 00000010 00000011 2, 3 शेष की गिनती e से होती है
g = f0 + f4 00000100 00000101 4, 5 प्रत्येक 8-बिट स्लाइस में 1s की गिनती
h0 = (g >> 0) & 0000000011111111 0000000000000101 5 g से प्रत्येक अन्य गिनती
h8 = (g >> 8) & 0000000011111111 0000000000000100 4 शेष की गणना g से की जाती है
i = h0 + h8 0000000000001001 9 संपूर्ण 16-बिट शब्द में 1s की गिनती

यहां, ऑपरेशन सी (प्रोग्रामिंग भाषा) के समान हैं X >> Y का अर्थ है X को Y बिट्स द्वारा दाईं ओर स्थानांतरित करना, X और Y का अर्थ है X और Y का बिटवाइज़, और + सामान्य जोड़ है। इस समस्या के लिए ज्ञात सर्वोत्तम एल्गोरिदम ऊपर चित्रित अवधारणा पर आधारित हैं और यहां दिए गए हैं:[1] 

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
int popcount64a(uint64_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
int popcount64b(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
int popcount64c(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

उपरोक्त कार्यान्वयन में किसी भी ज्ञात एल्गोरिदम की तुलना में सबसे व्यर्थ स्थिति वाला व्यवहार है। चूँकि, जब किसी मान में कुछ गैर-शून्य बिट्स होने की अपेक्षा होती है, तो इसके अतिरिक्त एल्गोरिदम का उपयोग करना अधिक कुशल हो सकता है जो इन बिट्स को समय में गिनता है। जैसा कि वेगनर ने 1960 में वर्णित किया था,[14] x के साथ x का बिटवाइज़ AND - 1 केवल सबसे कम महत्वपूर्ण गैर-शून्य बिट को शून्य करने में x से भिन्न होता है: 1 घटाने से 0s की सबसे दाईं स्ट्रिंग को 1s में बदल दिया जाता है, और सबसे दाईं ओर 1 को 0 में बदल दिया जाता है। यदि x में मूल रूप से n बिट्स थे जो थे 1, तो इस ऑपरेशन के केवल n पुनरावृत्तियों के बाद, x शून्य हो जाता है। निम्नलिखित कार्यान्वयन इसी सिद्धांत पर आधारित है। 

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

यदि अधिक मेमोरी उपयोग की अनुमति है, जिससे हम उपरोक्त विधियों की तुलना में हैमिंग वेट की तेजी से गणना कर सकते हैं। असीमित मेमोरी के साथ, हम आसानी से प्रत्येक 64 बिट पूर्णांक के हैमिंग वेट की बड़ी लुकअप तालिका बना सकते हैं। यदि हम प्रत्येक 16 बिट पूर्णांक के हैमिंग फ़ंक्शन की लुकअप तालिका संग्रहीत कर सकते हैं, जिससे हम प्रत्येक 32 बिट पूर्णांक के हैमिंग वेट की गणना करने के लिए निम्नलिखित कार्य कर सकते हैं। 

static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
//This algorithm uses 3 arithmetic operations and 2 memory reads.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Optionally, the wordbits[] table could be filled using this function
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++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i] = count;
    }
}

मुला एट अल.[15] दिखाया गया है कि पॉपकाउंट 64b का वेक्टरकृत संस्करण समर्पित निर्देशों (उदाहरण के लिए, x64 प्रोसेसर पर पॉपसीएनटी) की तुलना में तेजी से चल सकता है।

न्यूनतम वेट

त्रुटि-सुधार कोड या त्रुटि-सुधार कोडिंग में, न्यूनतम हैमिंग वेट, जिसे सामान्यतः न्यूनतम वेट wmin कहा जाता है कोड का वेट सबसे कम वेट वाले गैर-शून्य कोड शब्द का होता है। किसी कोड शब्द का भार w शब्द में 1s की संख्या है। उदाहरण के लिए, शब्द 11001010 का भार 4 है।

एक रैखिक ब्लॉक कोड में न्यूनतम वेट भी न्यूनतम हैमिंग दूरी (dmin) है और कोड की त्रुटि सुधार क्षमता को परिभाषित करता है। यदि wmin= n, फिर dmin= n और कोड dmin/2 त्रुटियाँ तक सही हो जाता है.[16]

भाषा समर्थन

कुछ सी कंपाइलर आंतरिक कार्य प्रदान करते हैं जो बिट गिनती की सुविधा प्रदान करते हैं। उदाहरण के लिए, जीएनयू कंपाइलर संग्रह (अप्रैल 2004 में संस्करण 3.4 से) में अंतर्निहित फ़ंक्शन सम्मिलित है __builtin_popcount यदि उपलब्ध हो तो यह प्रोसेसर निर्देश का उपयोग करेगा या अन्यथा कुशल लाइब्रेरी कार्यान्वयन का उपयोग करता है।[17] एलएलवीएम या एलएलवीएम-जीसीसी ने जून 2005 में संस्करण 1.5 से इस फ़ंक्शन को सम्मिलित किया है।[18]

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() सेट बिट्स की संख्या गिनने की विधि यह कार्यक्षमता अक्टूबर 2021 में जारी पायथन 3.10 में प्रस्तुत की गई थी।[19] सामान्य लिस्प में, फ़ंक्शन logcount, गैर-ऋणात्मक पूर्णांक दिया गया है, इस प्रकार 1 बिट्स की संख्या लौटाता है। (ऋणात्मक पूर्णांकों के लिए यह 2 के पूरक संकेतन में 0 बिट्स की संख्या लौटाता है।) किसी भी स्थिति में पूर्णांक बिग्नम हो सकता है।

ग्लासगो हास्केल कंपाइलर 7.4 से प्रारंभ होकर, हास्केल (प्रोग्रामिंग भाषा) बेस पैकेज में है popCount फ़ंक्शन सभी प्रकार के उदाहरणों पर उपलब्ध है Bits कक्षा (से उपलब्ध है Data.Bits मापांक)।[20]

एसक्यूएल भाषा का मायएसक्यूएल संस्करण प्रदान करता है BIT_COUNT() मानक फ़ंक्शन के रूप में।[21]

फोरट्रान 2008 में मानक, आंतरिक, मौलिक कार्य है popcnt पूर्णांक (या पूर्णांक सरणी) के अन्दर गैर-शून्य बिट्स की संख्या वापस करता है।[22]

कुछ प्रोग्रामयोग्य वैज्ञानिक पॉकेट कैलकुलेटर सेट बिट्स की संख्या की गणना करने के लिए विशेष कमांड की सुविधा देते हैं, उदाहरण के लिए #B एचपी-16सी पर [3][23] और WP 43S,[24][25] #BITS[26][27]या BITSUM [28][29] एचपी-16सी एमुलेटर पर, और nBITS WP 34S पर होता है.[30][31]

फ्रीपास्कल संस्करण 3.0 से पॉपसीएनटी प्रयुक्त करता है।[32]

प्रोसेसर समर्थन

  • 1960 के दशक में आईबीएम स्ट्रेच कंप्यूटर ने सभी तार्किक परिचालनों के उप-उत्पाद के रूप में सेट बिट्स की संख्या के साथ-साथ अग्रणी शून्य की संख्या की गणना की थी।[1]
  • क्रे सुपरकंप्यूटर में प्रारंभ में जनसंख्या गणना मशीन अनुदेश प्रदर्शित किया गया था, ऐसी अफवाह थी कि क्रिप्ट विश्लेषण अनुप्रयोगों के लिए अमेरिकी सरकार की राष्ट्रीय सुरक्षा एजेंसी द्वारा विशेष रूप से अनुरोध किया गया था।[1]
  • नियंत्रण डेटा निगम (सीडीसी) की सीडीसी 6000 श्रृंखला और सीडीसी साइबर या साइबर 70/170 श्रृंखला की मशीनों में जनसंख्या गणना निर्देश सम्मिलित हैं; 60-बिट मशीनों के लिए कम्पास में, इस निर्देश को इस प्रकार CXi. कोडित किया गया था
  • 64-बिट स्पार्क संस्करण 9 आर्किटेक्चर परिभाषित करता है POPC निर्देश,[12][1] किन्तु अधिकांश कार्यान्वयन इसे प्रयुक्त नहीं करते हैं, जिसके लिए ऑपरेटिंग सिस्टम द्वारा इसका अनुकरण करना आवश्यक होता है।[33]
  • डोनाल्ड नुथ का मॉडल कंप्यूटर [[एमएमआईएक्स]] जो अपनी पुस्तक कंप्यूटर प्रोग्रामिंग की कला में एमआएक्स का स्थान लेने जा रहा है, उसमें है SADD 1999 से निर्देश SADD a,b,c सभी बिट्स को गिनता है जो b में 1 और c में 0 हैं और परिणाम को a में लिखता है।
  • 1999 में जारी कॉम्पैक का अल्फा 21264A, पहला अल्फा श्रृंखला सीपीयू डिज़ाइन था जिसमें काउंट एक्सटेंशन था (CIX).
  • एनालॉग डिवाइस के ब्लैकफ़िन प्रोसेसर की सुविधा है ONES 32-बिट जनसंख्या गणना करने का निर्देश होता है।[34]
  • एएमडी के एएमडी K10 आर्किटेक्चर ने उन्नत बिट मैनिपुलेशन (एबीएम) निर्देश समुच्चय की प्रारंभ की POPCNT 2007 में एसएसई4ए एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया है।
  • इण्टेल कोर प्रोसेसर प्रस्तुत किया गया POPCNT एसएसई4.2 इंस्ट्रक्शन सेट एक्सटेंशन के साथ निर्देश, पहली बार नेहलेम (माइक्रोआर्किटेक्चर)-आधारित कोर i7 प्रोसेसर में उपलब्ध है, जो नवंबर 2008 में जारी किया गया था।
  • एआरएम आर्किटेक्चर की प्रारंभ की गई VCNT एआरएम एडवांस्ड सिमड (नियोन (निर्देश सेट) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है।
  • आरआईएससी-वी आर्किटेक्चर की प्रारंभ की गई PCNT बिट मैनिपुलेशन (b) एक्सटेंशन के भाग के रूप में निर्देश का उपयोग किया जाता है।[35]

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. pp. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
  2. ↑ Knuth, Donald Ervin (2009). "Bitwise tricks & techniques; Binary Decision Diagrams". The Art of Computer Programming. Vol. 4, Fascicle 1. Addison–Wesley Professional. ISBN 978-0-321-58050-4. (NB. Draft of Fascicle 1b available for download.)
  3. ↑ 3.0 3.1 Hewlett-Packard HP-16C Computer Scientist Owner's Handbook (PDF). Hewlett-Packard Company. April 1982. 00016-90001. Archived (PDF) from the original on 2017-03-28. Retrieved 2017-03-28.
  4. ↑ [1], written in Fōrmulæ. The Fōrmulæ wiki. Retrieved 2019-09-30.
  5. ↑ A solution to the task Population count. Retrieved 2019-09-30.
  6. ↑ Rosetta Code. Retrieved 2019-09-30.
  7. ↑ Thompson, Thomas M. (1983). From Error-Correcting Codes through Sphere Packings to Simple Groups. The Carus Mathematical Monographs #21. The Mathematical Association of America. p. 33.
  8. ↑ Glaisher, James Whitbread Lee (1899). "On the residue of a binomial-theorem coefficient with respect to a prime modulus". The Quarterly Journal of Pure and Applied Mathematics. 30: 150–156. (NB. See in particular the final paragraph of p. 156.)
  9. ↑ Reed, Irving Stoy (1954). "A Class of Multiple-Error-Correcting Codes and the Decoding Scheme". IRE Professional Group on Information Theory. Institute of Radio Engineers (IRE). PGIT-4: 38–49.
  10. ↑ Cohen, Gérard D.; Lobstein, Antoine; Naccache, David; Zémor, Gilles (1998). "How to improve an exponentiation black-box". In Nyberg, Kaisa (ed.). Advances in Cryptology – EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 – June 4, 1998, Proceeding. Lecture Notes in Computer Science. Vol. 1403. Springer. pp. 211–220. doi:10.1007/BFb0054128.
  11. ↑ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D. R.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (February 2003). "Chord: a scalable peer-to-peer lookup protocol for internet applications". IEEE/ACM Transactions on Networking. 11 (1): 17–32. doi:10.1109/TNET.2002.808407. S2CID 221276912. Section 6.3: "In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query."
  12. ↑ 12.0 12.1 SPARC International, Inc. (1992). "A.41: Population Count. Programming Note". The SPARC architecture manual: version 8 (Version 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 0-13-825001-4.
  13. ↑ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (eds.). "Record linkage by bit pattern matching". Computer Science and Statistics--Tenth Annual Symposium on the Interface. NBS Special Publication. U.S. Department of Commerce / National Bureau of Standards. 503: 146–156.
  14. ↑ Wegner, Peter (May 1960). "A technique for counting ones in a binary computer". Communications of the ACM. 3 (5): 322. doi:10.1145/367236.367286. S2CID 31683715.
  15. ↑ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (January 2018). "Faster Population Counts Using AVX2 Instructions". Computer Journal. 61 (1): 111–120. arXiv:1611.07612. doi:10.1093/comjnl/bxx046. S2CID 540973.
  16. ↑ Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
  17. ↑ "GCC 3.4 Release Notes". GNU Project.
  18. ↑ "LLVM 1.5 Release Notes". LLVM Project.
  19. ↑ "What's New In Python 3.10". python.org.
  20. ↑ "GHC 7.4.1 release notes". GHC documentation.
  21. ↑ "Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual".
  22. ↑ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4.
  23. ↑ Schwartz, Jake; Grevelle, Rick (2003-10-20) [1993]. HP16C Emulator Library for the HP48S/SX. 1.20 (1 ed.). Retrieved 2015-08-15. (NB. This library also works on the HP 48G/GX/G+. Beyond the feature set of the HP-16C this package also supports calculations for binary, octal, and hexadecimal floating-point numbers in scientific notation in addition to the usual decimal floating-point numbers.)
  24. ↑ Bonin, Walter (2019) [2015]. WP 43S Owner's Manual (PDF). 0.12 (draft ed.). p. 135. ISBN 978-1-72950098-9. Retrieved 2019-08-05. [2] [3] (314 pages)
  25. ↑ Bonin, Walter (2019) [2015]. WP 43S Reference Manual (PDF). 0.12 (draft ed.). pp. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Retrieved 2019-08-05. [4] [5] (271 pages)
  26. ↑ Martin, Ángel M.; McClure, Greg J. (2015-09-05). "HP16C Emulator Module for the HP-41CX - User's Manual and QRG" (PDF). Archived (PDF) from the original on 2017-04-27. Retrieved 2017-04-27. (NB. Beyond the HP-16C feature set this custom library for the HP-41CX extends the functionality of the calculator by about 50 additional functions.)
  27. ↑ Martin, Ángel M. (2015-09-07). "HP-41: New HP-16C Emulator available". Archived from the original on 2017-04-27. Retrieved 2017-04-27.
  28. ↑ Thörngren, Håkan (2017-01-10). "Ladybug Documentation" (release 0A ed.). Retrieved 2017-01-29. [6]
  29. ↑ "New HP-41 module available: Ladybug". 2017-01-10. Archived from the original on 2017-01-29. Retrieved 2017-01-29.
  30. ↑ Dale, Paul; Bonin, Walter (2012) [2008]. "WP 34S Owner's Manual" (PDF) (3.1 ed.). Retrieved 2017-04-27.
  31. ↑ Bonin, Walter (2015) [2008]. WP 34S Owner's Manual (3.3 ed.). ISBN 978-1-5078-9107-0.
  32. ↑ "Free Pascal documentation popcnt". Retrieved 2019-12-07.
  33. ↑ "JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h". Java bug database. 2006-01-30.
  34. ↑ Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.
  35. ↑ Wolf, Claire (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37" (PDF). Github.

अग्रिम पठन

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैमिंग_वेट&oldid=224029’