algorithm - हरण - पूर्णांक संख्या मराठी




32-बिट पूर्णांक में सेट बिट्स की संख्या को कैसे गिनें? (20)

संख्या 7 का प्रतिनिधित्व करने वाली 8 बिट्स इस तरह दिखती हैं:

00000111

तीन बिट सेट हैं।

32-बिट पूर्णांक में सेट बिट्स की संख्या निर्धारित करने के लिए एल्गोरिदम क्या हैं?


2 32 लुकअप टेबल के बीच एक सुखद माध्यम के लिए और अलग-अलग प्रत्येक बिट के माध्यम से पुनरावृत्ति:

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;
}

http://ctips.pbwiki.com/CountBits


अपने कंपाइलरों के अंतर्निर्मित कार्यों पर भी विचार करें।

उदाहरण के लिए जीएनयू कंपाइलर पर आप इसका उपयोग कर सकते हैं:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

सबसे खराब मामले में संकलक एक समारोह में एक कॉल उत्पन्न करेगा। सबसे अच्छे मामले में संकलक एक ही काम करने के लिए एक सीपीयू निर्देश उत्सर्जित करेगा।

जीसीसी इंट्रिनिक्स भी कई प्लेटफॉर्म पर काम करते हैं। पॉपकाउंट x86 आर्किटेक्चर में मुख्यधारा बन जाएगा, इसलिए अब आंतरिक का उपयोग शुरू करना समझ में आता है। अन्य वास्तुकला में वर्षों के लिए पॉपकाउंट है।

X86 पर, आप संकलक को बता सकते हैं कि यह popcnt निर्देश के लिए -mpopcnt या -msse4.2 साथ समर्थन -mpopcnt कर -msse4.2 है ताकि वे उसी पीढ़ी में जोड़े गए वेक्टर निर्देश भी सक्षम कर सकें। जीसीसी x86 विकल्प देखें। -march=nehalem (या- -march= जो भी सीपीयू आप अपने कोड को मानना ​​चाहते हैं और ट्यून करने के लिए चाहते हैं) एक अच्छा विकल्प हो सकता है। पुराने सीपीयू पर परिणामस्वरूप बाइनरी चलाने से अवैध-निर्देश गलती होगी।

जिस मशीन पर आप उन्हें बनाते हैं, उसके लिए द्विआधारी अनुकूलित करने के लिए, -march=native (जीसीसी, -march=native , या आईसीसी के साथ) का उपयोग करें।

popcnt x86 popcnt निर्देश के लिए एक आंतरिक प्रदान करता है , लेकिन जीसीसी के विपरीत यह वास्तव में हार्डवेयर निर्देश के लिए एक आंतरिक है और हार्डवेयर समर्थन की आवश्यकता है।

अंतर्निहित के बजाय std::bitset<>::count() का उपयोग करना

सिद्धांत रूप में, किसी भी कंपाइलर को जानता है कि लक्षित सीपीयू के लिए कुशलतापूर्वक पॉपकैंट कैसे करना चाहिए, उस कार्यक्षमता को आईएसओ सी ++ std::bitset<> माध्यम से प्रकट करना चाहिए। व्यावहारिक रूप से, आप कुछ लक्षित CPUs के लिए कुछ मामलों में बिट-हैक और / shift / ADD के साथ बेहतर हो सकते हैं।

लक्षित आर्किटेक्चर के लिए जहां हार्डवेयर पॉपकाउंट एक वैकल्पिक एक्सटेंशन (जैसे x86) है, सभी कंपलरों में एक std::bitset जो उपलब्ध होने पर इसका लाभ उठाता है। उदाहरण के लिए, popcnt संकलन समय पर popcnt समर्थन को सक्षम करने का कोई तरीका नहीं है, और हमेशा /Ox /arch:AVX साथ टेबल लुकअप का उपयोग करता है /Ox /arch:AVX (जो एसएसई 4.2 का तात्पर्य है, हालांकि तकनीकी रूप से popcnt लिए एक अलग फीचर बिट है।)

लेकिन कम से कम आपको कुछ पोर्टेबल मिलता है जो हर जगह काम करता है, और सही लक्ष्य विकल्पों के साथ जीसीसी / क्लैंग के साथ, आपको आर्किटेक्चर के लिए हार्डवेयर पॉपकाउंट मिलता है जो इसका समर्थन करता है।

#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();
}

गॉडबॉल्ट कंपाइलर एक्सप्लोरर पर जीसीसी, क्लैंग, आईसीसी, और एमएसवीसी से एएसएम देखें।

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 emits ( int arg संस्करण के लिए):

    rldicl 3,3,0,32     # zero-extend from 32 to 64-bit
    popcntd 3,3         # popcount
    blr

यह स्रोत x86- विशिष्ट या जीएनयू-विशिष्ट नहीं है, लेकिन केवल x86 के लिए gcc / clang / icc के साथ अच्छी तरह से संकलित करता है।

यह भी ध्यान रखें कि सिंगल-निर्देश पॉपकॉउंट के बिना आर्किटेक्चर के लिए जीसीसी की फॉलबैक एक बाइट-एट-टाइम टेबल लुकअप है। उदाहरण के लिए एआरएम के लिए यह अद्भुत नहीं है।


क्यों 2 से विभाजित नहीं?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

मैं मानता हूं कि यह सबसे तेज़ नहीं है, लेकिन "सर्वश्रेष्ठ" कुछ हद तक संदिग्ध है। मैं तर्क दूंगा कि "सर्वश्रेष्ठ" में स्पष्टता का तत्व होना चाहिए


जब आप बिट पैटर्न लिखते हैं तो हैकर का डिलाइट बिट-ट्विडलिंग इतना स्पष्ट हो जाता है।

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 को अंतिम गिनती न हो जाए।


मेरी राय में, "सर्वश्रेष्ठ" समाधान वह है जिसे किसी अन्य प्रोग्रामर (या दो साल बाद मूल प्रोग्रामर) द्वारा बिना किसी टिप्पणी के पढ़ा जा सकता है। आप सबसे तेज़ या चतुर समाधान चाहते हैं जो कुछ पहले ही प्रदान कर चुके हैं लेकिन मैं किसी भी समय चतुरता पर पठनीयता पसंद करता हूं।

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);
}

हालांकि ये विशिष्ट डेटा प्रकार के आकारों पर भरोसा करते हैं, इसलिए वे पोर्टेबल नहीं हैं। लेकिन, चूंकि कई प्रदर्शन अनुकूलन पोर्टेबल नहीं हैं, फिर भी यह कोई समस्या नहीं हो सकती है। यदि आप पोर्टेबिलिटी चाहते हैं, तो मैं पठनीय समाधान से चिपके रहूंगा।


मैं ऊब गया, और तीन दृष्टिकोणों के एक अरब पुनरावृत्तियों का समय लगा। कंपाइलर जीसीसी-ओ 3 है। सीपीयू जो भी उन्होंने पहली जेन मैकबुक प्रो में रखा है।

सबसे तेज़ है, 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] );
}

दूसरा स्थान एक ही कोड पर जाता है लेकिन 2 आधा शब्दों के बजाय 4 बाइट्स देखता है। इसमें लगभग 5.5 सेकंड लग गए।

तीसरा स्थान बिट-ट्विडलिंग 'किनारे के अतिरिक्त' दृष्टिकोण पर जाता है, जिसमें 8.6 सेकंड लगते थे।

चौथी जगह जीसीसी के __builtin_popcount () को शर्मनाक 11 सेकंड में जाती है।

गिनती एक-बिट-ए-ए-टाइम दृष्टिकोण कम धीमी थी, और मैं इसे पूरा करने के लिए इंतजार करने से ऊब गया।

तो यदि आप सभी के ऊपर प्रदर्शन के बारे में परवाह करते हैं तो पहले दृष्टिकोण का उपयोग करें। यदि आप परवाह करते हैं, लेकिन उस पर 64 केबी रैम खर्च करने के लिए पर्याप्त नहीं है, तो दूसरे दृष्टिकोण का उपयोग करें। अन्यथा पठनीय (लेकिन धीमी) एक-बिट-पर-एक-बार दृष्टिकोण का उपयोग करें।

ऐसी स्थिति के बारे में सोचना मुश्किल है जहां आप बिट-ट्विडलिंग दृष्टिकोण का उपयोग करना चाहते हैं।

संपादित करें: here इसी प्रकार के परिणाम।


यह उन प्रश्नों में से एक है जहां यह आपके सूक्ष्म वास्तुकला को जानने में मदद करता है। मैंने फ़ंक्शन कॉल ओवरहेड, एक बिलियन पुनरावृत्तियों को समाप्त करने के लिए सी ++ इनलाइनों का उपयोग करते हुए -ऑ 3 के साथ संकलित जीसीसी 4.3.3 के तहत दो प्रकारों का समय दिया, यह सुनिश्चित करने के लिए कि संकलक समय के लिए 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;
}

Unmodified हैकर की Delight 12.2 gigacycles लिया। मेरा समांतर संस्करण (कई बिट्स के रूप में दो बार गिनती) 13.0 गीगासीकल में चलता है। 2.4 गीगाहर्ट्ज कोर डुओ पर एक साथ दोनों के लिए कुल 10.5 गुना हो गया। 25 gigacycles = इस घड़ी आवृत्ति पर बस 10 सेकंड से अधिक, तो मुझे विश्वास है कि मेरे समय सही हैं।

इसे निर्देश निर्भरता श्रृंखला के साथ करना है, जो इस एल्गोरिदम के लिए बहुत खराब हैं। 64-बिट रजिस्टरों की एक जोड़ी का उपयोग करके मैं फिर से गति को दोगुना कर सकता था। असल में, अगर मैं चालाक था और एक्स + या थोड़ा जल्दी जोड़ा तो मैं कुछ बदलावों को बंद कर सकता था। कुछ छोटे tweaks के साथ 64-बिट संस्करण भी बाहर आ जाएगा, लेकिन दो बार गिनती दो बार गिनती है।

128 बिट सिम रजिस्टरों के साथ, फिर भी दो का एक और कारक, और एसएसई निर्देश सेटों में अक्सर चालाक शॉर्ट-कट भी होते हैं।

कोड विशेष रूप से पारदर्शी होने का कोई कारण नहीं है। इंटरफ़ेस सरल है, एल्गोरिदम को कई स्थानों पर ऑनलाइन संदर्भित किया जा सकता है, और यह व्यापक इकाई परीक्षण के लिए उपयुक्त है। प्रोग्रामर जो उस पर ठोकर खा सकता है वह कुछ भी सीख सकता है। मशीन स्तर पर ये बिट ऑपरेशंस बेहद स्वाभाविक हैं।

ठीक है, मैंने tweaked 64-बिट संस्करण बेंच करने का फैसला किया। इस आकार के लिए (हस्ताक्षरित लंबा) == 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 गीगासाइकिल / 14.1 गीगासीकल पर आ गया है। उस बाद के नंबर में 128 बिलियन बिट्स का सारांश दिया गया और इस मशीन पर 5.9 से गुजरने के अनुरूप है। गैर समांतर संस्करण एक छोटे से बिट को गति देता है क्योंकि मैं 64-बिट मोड में चल रहा हूं और इसे 32-बिट रजिस्टरों की तुलना में 64-बिट रजिस्टरों को थोड़ा बेहतर लगता है।

चलो देखते हैं कि यहां थोड़ी अधिक ओओओ पाइपलाइनिंग है या नहीं। यह थोड़ा और शामिल था, इसलिए मैंने वास्तव में थोड़ा परीक्षण किया। अकेले प्रत्येक शब्द 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;
}

मैं एक पल के लिए उत्साहित था, लेकिन यह पता चला कि जीसीसी इन-ओ 3 के साथ इनलाइन चाल चल रहा है, भले ही मैं कुछ परीक्षणों में इनलाइन कीवर्ड का उपयोग नहीं कर रहा हूं। जब मैंने जीसीसी प्ले ट्रिक्स को छोड़ दिया, तो पॉप 4 () में एक बिलियन कॉल 12.56 गीगासीकल लेते हैं, लेकिन मैंने निर्धारित किया कि यह लगातार अभिव्यक्ति के रूप में तर्कों को तब्दील कर रहा था। एक और यथार्थवादी संख्या 30% गति-अप के लिए 19.6 जीसी लगती है। मेरा टेस्ट लूप अब इस तरह दिखता है, यह सुनिश्चित करना कि प्रत्येक तर्क जीसीसी को चाल चलने से रोकने के लिए पर्याप्त है।

   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(); 

8.17 में उल्लिखित 256 अरब बिट्स बीत गए। 16-बिट टेबल लुकअप में बेंचमार्क किए गए 32 मिलियन बिट्स के लिए 1.02 तक काम करता है। सीधे तुलना नहीं कर सकते, क्योंकि अन्य खंडपीठ घड़ी की गति नहीं देता है, लेकिन ऐसा लगता है कि मैंने 64 केबी टेबल संस्करण से स्नॉट थप्पड़ मार दिया है, जो पहले स्थान पर एल 1 कैश का एक दुखद उपयोग है।

अद्यतन: चार और डुप्लिकेट लाइनों को जोड़कर स्पष्ट करने और pop6 () बनाने का निर्णय लिया। 22.8 जीसी तक पहुंचे, 38.5 अरब बिट्स 9.5 में गिर गए। तो 32 बिलियन बिट्स के लिए अब 800% पर 20% है।


यह सबसे तेज़ या सबसे अच्छा समाधान नहीं है, लेकिन मुझे वही प्रश्न मेरे रास्ते में मिला, और मैंने सोचना और सोचना शुरू कर दिया। finally I realized that it can be done like this if you get the problem from mathematical side, and draw a graph, then you find that it's a function which has some periodic part, and then you realize the difference between the periods... so here you go:

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);
    }
}

हैकर के डिलाइट से, पी। 66, चित्रा 5-2

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-आश निर्देशों (आर्क आश्रित) में निष्पादित, कोई शाखा नहीं।

हैकर की प्रसन्नता सुखद है! अत्यधिक सिफारिशित।


Fast C# solution using pre-calculated table of Byte bit counts with branching on input size.

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
    };
}

Here is a portable module ( ANSI-C ) which can benchmark each of your algorithms on any architecture.

Your CPU has 9 bit bytes? No problem :-) At the moment it implements 2 algorithms, the K&R algorithm and a byte wise lookup table. The lookup table is on average 3 times faster than the K&R algorithm. If someone can figure a way to make the "Hacker's Delight" algorithm portable feel free to add it in.

#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

I always use this in Competitive Programming and it's easy to write and efficient:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

I think the Brian Kernighan's method will be useful too... It goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

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; 
}

Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to me that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"


I use the below code which is more intuitive.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Logic : n & (n-1) resets the last set bit of n.

PS : I know this is not O(1) solution, albeit an interesting solution.


I'm particularly fond of this example from the fortune file:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

I like it best because it's so pretty!


Java JDK1.5

Integer.bitCount(n);

where n is the number whose 1's are to be counted.

check also,

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);
         }

There are many algorithm to count the set bits; but i think the best one is the faster one! You can see the detailed on this page:

Bit Twiddling Hacks

I suggest this one:

Counting bits set in 14, 24, or 32-bit words using 64-bit instructions

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;

This method requires a 64-bit CPU with fast modulus division to be efficient. The first option takes only 3 operations; the second option takes 10; and the third option takes 15.


This can be done in O(k) , where k is the number of bits set.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

if you're using C++ another option is to use template 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;
}

usage would be:

// 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 )

you could of course further expand this template to use different types (even auto-detecting bit size) but I've kept it simple for clarity.

edit: forgot to mention this is good because it should work in any C++ compiler and it basically just unrolls your loop for you if a constant value is used for the bit count (in other words, I'm pretty sure it's the fastest general method you'll find)


  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;
    }






iec10967