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




पूर्णांक संख्या मराठी (24)

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

00000111

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

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


What do you means with "Best algorithm"? The shorted code or the fasted code? Your code look very elegant and it has a constant execution time. The code is also very short.

But if the speed is the major factor and not the code size then I think the follow can be faster:

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

I think that this will not more faster for a 64 bit value but a 32 bit value can be faster.


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)


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.)"


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


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.


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!


यदि आप जावा का उपयोग करते हैं, तो अंतर्निहित विधि Integer.bitCount ऐसा करेगा।


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

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

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


The function you are looking for is often called the "sideways sum" or "population count" of a binary number. Knuth discusses it in pre-Fascicle 1A, pp11-12 (although there was a brief reference in Volume 2, 4.6.3-(7).)

The locus classicus is Peter Wegner's article "A Technique for Counting Ones in a Binary Computer", from the Communications of the ACM , Volume 3 (1960) Number 5, page 322 . He gives two different algorithms there, one optimized for numbers expected to be "sparse" (ie, have a small number of ones) and one for the opposite case.


I found an implementation of bit counting in an array with using of SIMD instruction (SSSE3 and AVX2). It has in 2-2.5 times better performance than if it will use __popcnt64 intrinsic function.

SSSE3 version:

#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 version:

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

Few open questions:-

  1. If the number is negative then?
  2. If the number is 1024 , then the "iteratively divide by 2" method will iterate 10 times.

we can modify the algo to support the negative number as follows:-

count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
    count += 1
  n /= 2  
return count

now to overcome the second problem we can write the algo like:-

int bit_count(int num)
{
    int count=0;
    while(num)
    {
        num=(num)&(num-1);
        count++;
    }
    return count;
}

for complete reference see :

http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html


मैं ऊब गया, और तीन दृष्टिकोणों के एक अरब पुनरावृत्तियों का समय लगा। कंपाइलर जीसीसी-ओ 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 इसी प्रकार के परिणाम।


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

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

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


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

मुझे इस एल्गोरिदम की व्याख्या करने दें।

यह एल्गोरिदम डिवाइड और जीत एल्गोरिदम पर आधारित है। मान लें कि 8 बिट पूर्णांक 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)
+-------------------------------+

32-bit or not ? I just came with this method in Java after reading " cracking the coding interview " 4th edition exercice 5.5 ( chap 5: Bit Manipulation). If the least significant bit is 1 increment count , then right-shift the integer.

public static int bitCount( int n){
    int count = 0;
    for (int i=n; i!=0; i = i >> 1){
        count += i & 1;
    }
    return count;
}

I think this one is more intuitive than the solutions with constant 0x33333333 no matter how fast they are. It depends on your definition of "best algorithm" .


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

I wrote a fast bitcount macro for RISC machines in about 1990. It does not use advanced arithmetic (multiplication, division, %), memory fetches (way too slow), branches (way too slow), but it does assume the CPU has a 32-bit barrel shifter (in other words, >> 1 and >> 32 take the same amount of cycles.) It assumes that small constants (such as 6, 12, 24) cost nothing to load into the registers, or are stored in temporaries and reused over and over again.

With these assumptions, it counts 32 bits in about 16 cycles/instructions on most RISC machines. Note that 15 instructions/cycles is close to a lower bound on the number of cycles or instructions, because it seems to take at least 3 instructions (mask, shift, operator) to cut the number of addends in half, so log_2(32) = 5, 5 x 3 = 15 instructions is a quasi-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;

Here is a secret to the first and most complex step:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

so if I take the 1st column (A) above, shift it right 1 bit, and subtract it from AB, I get the output (CD). The extension to 3 bits is similar; you can check it with an 8-row boolean table like mine above if you wish.

  • Don Gillies

मुझे लगता है कि लुकअप टेबल और पॉपकाउंट का उपयोग किए बिना सबसे तेज़ तरीका - निम्नलिखित में। यह सेट 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 रूप में भी जानें 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 उत्पन्न 0b01 , तो यह 0b00 उत्पन्न 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 । इसका मतलब है कि पहले निबल के 4 बिट सेट हैं और दूसरे के पास 2 बिट सेट हैं। अब हम उन निबल्स को एक साथ जोड़ते हैं।

0b01000010 + 0b01000000

यह हमें पहले 0b01100010 में एक बाइट में सेट बिट्स की गिनती देता है और इसलिए हम संख्या में सभी बाइट्स के अंतिम चार बाइट्स (उन्हें छोड़कर) मास्क करते हैं।

0b01100010 & 0xF0 = 0b01100000

अब हर बाइट में सेट बिट्स की गिनती है। हमें उन्हें एक साथ जोड़ना होगा। यह चाल 0b10101010 द्वारा परिणाम को गुणा करना है जिसमें एक दिलचस्प संपत्ति है। यदि हमारे नंबर में चार बाइट्स हैं, ABCD , तो इसके परिणामस्वरूप इन बाइट्स A+B+C+D B+C+D C+DD साथ एक नया नंबर होगा। एक 4 बाइट नंबर में अधिकतम 32 बिट सेट हो सकते हैं, जिन्हें 0b00100000 रूप में 0b00100000 किया जा सकता है।

हमें बस इतना पहले बाइट है जिसमें सभी बाइट्स में सभी सेट बिट्स का योग है, और हम इसे >> 24 प्राप्त करते हैं। यह एल्गोरिदम 32 bit शब्दों के लिए डिज़ाइन किया गया था लेकिन 64 bit शब्दों के लिए आसानी से संशोधित किया जा सकता है।


इसे ' हैमिंग वेट ', 'पॉपकाउंट' या 'किनारे के अतिरिक्त' के रूप में जाना जाता है।

'सर्वश्रेष्ठ' एल्गोरिदम वास्तव में इस बात पर निर्भर करता है कि आप किस सीपीयू पर हैं और आपका उपयोग पैटर्न क्या है।

कुछ CPUs में ऐसा करने के लिए एक अंतर्निहित निर्देश होता है और अन्य के समानांतर निर्देश होते हैं जो बिट वैक्टर पर कार्य करते हैं। समांतर निर्देश (जैसे कि x86 के popcnt , सीपीयू पर जहां यह समर्थित है) लगभग निश्चित रूप से सबसे तेज़ होगा। कुछ अन्य आर्किटेक्चर में एक धीमी निर्देश हो सकती है जो एक माइक्रोक्रॉइड लूप के साथ लागू होती है जो थोड़ा सा चक्र ( उद्धरण वांछित ) का परीक्षण करती है।

यदि आपके सीपीयू में एक बड़ा कैश है और / या आप इन निर्देशों को एक तंग लूप में कर रहे हैं तो एक पूर्व-पॉप्युलेटेड टेबल लुकअप विधि बहुत तेज हो सकती है। हालांकि यह 'कैश मिस' की कीमत के कारण पीड़ित हो सकता है, जहां सीपीयू को मुख्य मेमोरी से कुछ टेबल लेना पड़ता है।

यदि आप जानते हैं कि आपके बाइट अधिकतर 0 या अधिकतर 1 होंगे तो इन परिदृश्यों के लिए बहुत ही कुशल एल्गोरिदम हैं।

मेरा मानना ​​है कि एक बहुत अच्छा सामान्य उद्देश्य एल्गोरिदम निम्न है, जिसे 'समानांतर' या 'चर-परिशुद्धता स्वार एल्गोरिदम' कहा जाता है। मैंने इसे सी-जैसी छद्म भाषा में व्यक्त किया है, आपको इसे किसी विशेष भाषा के लिए काम करने के लिए समायोजित करने की आवश्यकता हो सकती है (उदाहरण के लिए जावा में सी ++ और >>> के लिए uint32_t का उपयोग करना):

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

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

सिमड के साथ सीपीयू पर एक गति के लिए, लेकिन एक उपयोग करने योग्य पॉपकाउंट निर्देश के लिए, यह बिटवाई-स्वैर एल्गोरिदम एक ही इंटीजर रजिस्टर की बजाय, एकाधिक वेक्टर तत्वों में एक साथ में समानांतर हो सकता है। (उदाहरण के लिए x86-64 कोड जिसे किसी भी सीपीयू पर चलाना है, न कि केवल नेहलेम या बाद में।)

हालांकि, पॉपकैंट के लिए वेक्टर निर्देशों का उपयोग करने का सबसे अच्छा तरीका आम तौर पर समानांतर में प्रत्येक बाइट के समय 4 बिट्स के लिए टेबल-लुकअप करने के लिए एक चर-शफल का उपयोग करके होता है। (4 बिट्स इंडेक्स एक वेक्टर रजिस्टर में आयोजित 16 प्रविष्टि तालिका)।

इंटेल सीपीयू पर, हार्डवेयर 64 बिट पॉपकंट निर्देश एसएसएसई 3 PSHUFB बिट-समांतर कार्यान्वयन को 2 के कारक से बेहतर प्रदर्शन कर सकता है, लेकिन केवल तभी जब आपका कंपाइलर इसे सही हो । अन्यथा एसएसई काफी आगे आ सकता है। नए कंपाइलर संस्करण इंटेल पर popcnt झूठी निर्भरता समस्या से अवगत हैं।

संदर्भ:

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(Ones%20Count)


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

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


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

यह सबसे तेज़ या सबसे अच्छा समाधान नहीं है, लेकिन मुझे वही प्रश्न मेरे रास्ते में मिला, और मैंने सोचना और सोचना शुरू कर दिया। 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);
    }
}

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

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

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 के साथ अच्छी तरह से संकलित करता है।

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





iec10967