32 bit tamsayıdakı bitlərin sayını necə hesablamaq olar?

7 sayını təmsil edən 8 bit aşağıdakılardır:

 00000111 

Üç bit müəyyən edilir.

32 bit tamsayıda göstərilən bit sayını müəyyənləşdirmək üçün alqoritmlər hansılardır?

767
20 сент. Matt Howells tərəfindən təyin olunan 20 sentyabr. 2008-09-20 22:04 '08 saat 10:04 'da 2008-09-20 22:04
@ 50 cavab
  • 1
  • 2

Buna " ağırlıq çəkən", "popcount" və ya "yan əlavə" deyilir.

"Ən yaxşı" alqoritm, həqiqətən, hansı prosessordan və hansı istifadə modelindən asılıdır.

Bəzi CPU'lar birbaşa daxili göstərişə malikdir, digərləri bit vektorlarında hərəkət edən paralel təlimatlara malikdirlər. Paralel təlimatlar (məsələn, x86 popcnt , dəstəkləndiyi prosessorlarda) demək olar ki, ən sürətli olacaqdır. Bəzi digər memarlar, dövrəyə bitləri yoxlayan bir mikrokod loopu ilə tətbiq olunan yavaş təlimata malik ola bilər (tırnak lazımdır).

Masanın doldurulmuş bir masa ilə doldurulması üsulu, prosessorunuzun böyük bir önbellek varsa və / və ya bu təlimatların bir çoxunu sıx bir dövrə ilə yerinə yetirirsinizsə, çox sürətli ola bilər. Bununla yanaşı CPU əsas yaddaşdan bir hissəsini çıxarması lazım olduğu zaman "cache miss" xərcləri səbəbindən əziyyət çəkir.

Əgər baytlarınız əsasən 0 və ya daha çox 1 olacağını bilsəniz, bu ssenarilər üçün çox səmərəli alqoritmlər var.

İnanıram ki, çox yaxşı bir ümumi məqsədi alqoritm "paralel" və ya "dəyişən həssas SWAR alqoritmi" kimi tanınır. Mən bunu C-tipli sözdə ifadə etmişəm, müəyyən bir dildə işləmək üçün onu konfiqurasiya etməliyik (məsələn, uint32_t istifadə C ++ və → → Java-da):

SSSE3 PSHUFB bit-paralel tətbiqini təxminən 2 dəfə PSHUFB bilər, ancaq yalnız tərtibatçının onu doğru bir şəkildə alır .  Əks halda, SSE çox irəlidə gedə bilər.  Kompilyatorun yeni versiyaları Intel-saxta asılılıq popcnt problemindən xəbərdardır. 

Ədəbiyyat:

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)

772
20 сент. Matt Howells tərəfindən verilmiş cavab 20 sentyabr 2008-09-20 22:05 '08 at 10:05 pm 2008-09-20 22:05

Ayrıca derleyicilerinizin daxili funksiyalarını da nəzərə alın.

Məsələn, GNU tərtibçisində, sadəcə istifadə edə bilərsiniz:

GCC x86 variantlarına baxın.  -march=nehalem (və ya -march= kodu qəbul etmək və konfiqurasiya etmək istədiyiniz hər hansı bir prosessor) yaxşı seçim ola bilər.  Yaranan ikili köhnə bir prosessor üzərində işləyərkən səhv göstəriş ilə səhv olur. 

-march=native maşın üçün optimize etmək üçün, -march=native (gcc, -march=native və ya ICC ilə) istifadə edin.

MSVC daxili x86 popcnt təmin edir , lakin gcc-dan fərqli olaraq, bu hardware təlimatının ayrılmaz bir hissəsidir və hardware dəstək tələb edir.


std::bitset<>::count() istifadə edərək yerləşdirin

border=0

Teorik olaraq, hədəf CPU üçün məlumatları effektiv şəkildə yığa bilən hər hansı bir kompilyator bu funksiyanı ISO C ++ std::bitset<> vasitəsilə açıqlamalıdır. Praktikada, bəzi hədəf CPU'lar üçün bəzi hallarda bit-qırılma və / shift / ADD ilə daha yaxşı ola bilər.

Hədəf mimarisi üçün, donanım popcountunun isteğe bağlı bir uzantı olduğu (məsələn, x86) olduğu üçün, bütün kompilyatorlar mövcud olduqda istifadə edən std::bitset deyil. Məsələn, MSVC popcnt zamanı popcnt dəstəyi təmin etmək imkanı yoxdur və həmişə /Ox /arch:AVX (SSE4.2 nəzərdə tutur, baxmayaraq ki, texniki cəhətdən popcnt üçün ayrı funksiya biti var).

Amma ən azından bütün yerlərdə işləyən portativ bir şey alırsınız və doğru hədəf parametrləri ilə gcc / c>

Godbold kompilyatorunda gcc, c> - dən asm baxın. 

x86-64 gcc -O3 -std=gnu++11 -mpopcnt bunu gcc -O3 -std=gnu++11 -mpopcnt :

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

Bu mənbə x86 və ya GNU-ya xüsusi deyil, yalnız gcc / c>

Həmçinin, bir istifadəçi popcount arxitekturasının gcc-i dəstəkləməsi zamanla bayt axtarışdır. Məsələn, ARM üçün təəccüblü deyil.

188
20 сент. Cavab Nils Pipenbrinck tərəfindən verilib. 2008-09-20 22:23 '08 at 22:23 pm 2008-09-20 22:23

Mənim fikrimcə, "ən yaxşı" həlli bir proqramçı (ya iki il sonra orijinal proqramçı) tərəfindən çox oxunuş olmadan oxuya bilən bir şeydir. Bəziləri artıq təmin etdiyimiz ən qısa və ya ağıllı bir həllə ehtiyac duya bilərsiz, amma istənilən vaxt bacarıqla bağlı oxunaqlılığı üstün tuturam.

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

Daha çox sürətə ehtiyacınız varsa (və sizin varislərinizə kömək etmək üçün sənəd verdiyiniz halda), axtarış masasını istifadə edə bilərsiniz:

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

Onlar xüsusi məlumat növlərinə etibar etsələr də, buna görə də portativ deyildirlər. Lakin, bir çox performans optimallaşdırması hər halda köçürülməmiş olduğundan, bu problem ola bilməz. Transfer etmək istəyirsinizsə, mən oxunaqlı bir həll qalmaq.

169
21 сент. cavab paxdiablo 21 sep verilir . 2008-09-21 04:14 '08 at 4:14 'da 2008-09-21 04:14

Hacker Delight-dən, s. 66, Şəkil 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; } 

Dəmir yolu olmadan ~ 20 talimatında (kemerdən asılı olaraq) icra olunur.

Hacker zövqü inanılmazdır! Tövsiyə olun.

94
20 сент. Cavab Kevin Little tərəfindən verilir 20 Sep. 2008-09-20 22:38 '08 at 10:38 pm 2008-09-20 22:38

Hesab edirəm ki, ən tez yol - masa masaları və popcount istifadə etmədən - belədir. Set bitlərini sadəcə 12 əməliyyatda sayar.

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

Bu, hər iki yarımda müəyyən olunmuş bit sayını hesablayaraq onları əlavə edərək, onları iki yarıya bölməklə təyin olunmuş bit sayını hesablaya biləcəyiniz üçün işləyir. Divide and Conquer paradiqması kimi tanınır. Daha nəzər salaq.

 v = v - ((v >> 1)  0x55555555); 

İki bitlik bit 0b00 , 0b01 və ya 0b10 ola bilər. 2 bitə ayırmaq üçün cəhd edək.

  --------------------------------------------- | v | (v >> 1)  0b0101 | v - x | --------------------------------------------- 0b00 0b00 0b00 0b01 0b00 0b01 0b10 0b01 0b01 0b11 0b01 0b10 

Lazım olan bu: son sütun hər bit cütündə müəyyən edilmiş bit sayını göstərir. İki bit sayı >= 2 (0b10) , 0b01 , əks halda 0b00 .

 v = (v  0x33333333) + ((v >> 2)  0x33333333); 

Bu bəyanat asanlıqla başa düşülməlidir. İlk əməliyyatdan sonra hər bitdə bir az sayğacımız var, indi bu hesabı hər 4 bitdə yekunlaşdırırıq.

 v  0b00110011 //masks out even two bits (v >> 2)  0b00110011 // masks out odd two bits 

Sonra biz 4 bitin bir dəstinin bit sayını verərək yuxarıdakı nəticəni ümumiləşdiririk. Son bəyanat ən çətindir.

 c = ((v + (v >> 4)  0xF0F0F0F) * 0x1010101) >> 24; 

Daha da qırılsınlar ...

 v + (v >> 4) 

Bu ikinci ifadəyə bənzəyir; Bunun əvəzinə, 4-cü qruplardakı bit qrupunu sayırıq. Əvvəlki əməliyyatlarımızdan görə - hər parça parçada olan bit sayına malikdir. Bir nümunə görək. Bir bayt 0b01000010 olduğunuzu varsayalım. Bu deməkdir ki, ilk nibble 4 bitə, ikincisi isə 2 bitə malikdir. İndi bu ədədləri birlikdə əlavə edirik.

 0b01000010 + 0b01000000 

Bu, 0b01100010 ilk nibble-da 0b01100010 bit sayını 0b01100010 və bu səbəbdən 0b01100010 bütün baytlarının son 4 0b01100010 mask edirik.

 0b01100010  0xF0 = 0b01100000 

İndi hər baytda bir az sayğac var. Onları bir yerə əlavə etməliyik. Oyunun nəticəsi 0b10101010 ilə maraqlı bir əmlaka 0b10101010 . ABCD , dörd ədəd baytımız varsa, bu, bu bayt A+B+C+D B+C+D C+DD ilə yeni bir rəqəmin ortaya A+B+C+D B+C+D C+DD . 4 bayta 32 0b00100000 ola bilər, bu da 0b00100000 kimi təqdim edilə bilər.

İndi bütün baytlarda verilən bütün bitlərin məbləğinə sahib olan ilk bayta ehtiyacımız var və biz onu alırıq >> 24 . Bu alqoritm 32 bit sözlər üçün hazırlanmış, lakin 64 bit sözlər üçün asanlıqla dəyişdirilə bilər.

70
12 апр. cavab 12 aprda verilir . 2013-04-12 22:14 '13 saat 10:14 'da 2013-04-12 22:14

Mən üç dəfə yanaşdıq və bir milyard iterasiyaya vaxt verdim. Derleyici, gcc-O3'dür. CPU'lar 1. Gen MacBook Pro'unu gətirirlər.

Onların ən sürətli: 3.7 saniyə:

 static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 }; static int popcount( unsigned int i ) { return( wordbits[i + wordbits[i>>16] ); } 

İkincisi isə eyni koda aiddir, lakin 2 yarım söz yerinə 4 baytlıq axtarış aparır. Bu təxminən 5,5 saniyə çəkdi.

Üçüncü yer 8,6 saniyə çəkən yanal yerdəyişmə ilə yanaşmaya aiddir.

Dördüncüsü GCC __builtin_popcount (), utancaq 11 saniyə çəkir.

Hər bir ikinci üsuldan istifadə edərək hesablama yavaş idi və mən başa çatdırılmasını gözləyirdim.

Beləliklə, əgər başqalarından üstün performansa diqqət yetirsəniz, ilk yanaşmanı istifadə edin. Xahiş etmirsinizsə, ancaq 64 KB RAM sərf etmək üçün kifayət etmirsə, ikinci yanaşmanı istifadə edin. Əks təqdirdə oxunaqlı (lakin yavaş) tək bit anlayışından istifadə edin.

Bir az əsaslı yanaşma istifadə etmək istədiyiniz bir vəziyyət barədə düşünmək çətindir.

Düzenle: burada oxşar nəticələr.

54
25 сент. Cavab Mike F sentyabr 25-də verilir. 2008-09-25 05:46 '08 saat 05:46 'da 2008-09-25 05:46

Java istifadə edirsinizsə, daxili üsul Integer.bitCount bunu edəcək.

52
20 сент. Cavab 20 sentyabr tərəfindən Noether tərəfindən verilir. 2008-09-20 22:14 '08 at 10:14 pm 2008-09-20 22:14
 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; } 

Mənə bu alqoritmi izah edək.

Bu alqoritm Divide və Conquer alqoritminə əsaslanır. 8 bitlik tam ədəd 213 (ikili şəklində 11010101) olduğunu düşünsəniz, alqoritm bu kimi işləyir (hər dəfə iki qonşu blokun birləşməsi):

 +-------------------------------+ | 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) +-------------------------------+ 
29
05 авг. Cavab abcdabcd987 05 avqustda verilir . 2012-08-05 15:47 '12 at 3:47 pm 2012-08-05 15:47

Mikro-arxitekturanı bilmək üçün bu suallardan biridir. GCC 4.3.3-də C3 + ilə tərtib edilmiş iki seçim variantını, C ++ inline istifadə edərək, funksiya çağırışlarını aradan qaldırmaq üçün, bir milyard iterasiyanı silmək, kompilyatorun əhəmiyyətli bir şeyi aradan qaldırmadığını təmin etmək üçün bütün cədvəllərin saxlanmasını təmin edirəm. sinxronizasiya üçün rdtsc istifadə (saat dövrü).

 inline int pop2 (imzalanmamış x, imzalanmamış y) { x = x - ((x >> 1) və 0x55555555); y = y - ((y> 1)  0x55555555); x = (x  0x33333333) + ((x >> 2)  0x33333333); y = (y  0x33333333) + ((y> 2)  0x33333333); x = (x + (x >> 4)) və 0x0F0F0F0F; y = (y + (y> 4)) və 0x0F0F0F0F; x = x + (x >> 8); y = y + (y> 8); x = x + (x> 16); y = y + (y> 16); return (x + y) və 0x000000FF; }

Değişməmiş hacker ləzzəti 12.2 gigalicles aldı. Mənim paralel versiyam (iki dəfə çox sayda sayılır) 13.0 gigacycles işləyir. Yalnız 2,4 GHz Core Duo'da birləşdirilmişdir. 25 gigacycles = bu saat tezliyində 10 saniyədən çoxdur, buna görə də əminəm ki, vaxtlarım düzgündür.

Bu, bu alqoritm üçün çox pis olan komanda bağımlılıklarının zənciri ilə bağlıdır. Bir neçə 64-bit reyestrdən istifadə edərək sürəti daha da cütləşdirə bilərəm. Əslində, ağıllıysam və bir qədər əvvəl x + y əlavə etsəm, bəzi dəyişiklikləri qırxardı. Bəzi kiçik parametrlərə malik olan 64-bit versiyası hamar bir şəkildə çıxacaq, lakin iki dəfə çox bit yenidən hesablanacaq.

128-bit SIMD qeydləri ilə, iki başqa bir amil və SSE komanda tez-tez də ağıllı qısa yollara malikdir.

Kodun xüsusilə şəffaf olması üçün heç bir səbəb yoxdur. İnterfeys sadədir, alqoritm çox yerlərdə online istinad edilə bilər və özünü hərtərəfli vahid testinə verir. Ona çarparaq bir proqramçı hətta bir şey öyrənə bilər. Bu bit əməliyyatları maşın səviyyəsində olduqca təbiidir.

Tamam, bir atlama 64-bit versiyasını çalıştırmaya qərar verdim. Bu bir ölçüsü üçün (imzalanmamış uzun) == 8

 inline int pop2 (imzalanmayan uzun x, imzalanmamış uzun 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);  x  0xFF qayıtmaq; }

Doğru görünür (çox diqqətlə test etmirəm). Artıq 10,70 gigalicles / 14,1 gigalicles gedir. Bu sonrakı sayda 128 milyard bit əlavə edilmiş və bu maşında keçən 5.9-a bərabərdir. Qeyri-paralel versiya, 64 bit rejimində işlədiyim üçün 64 bitlik qeydiyyatdan 32 bit qeydiyyatdan bir az daha yaxşıdır.

Bir neçə boru kəməri MMC-nin olub olmadığını görək. Bir az daha aktiv idi, buna görə bir az test etdik. Öz içində hər bir üzv özünə 64 verilir, bütün birləşmənin miqdarı isə 256.

 inline int pop4 (imzalanmayan uzun x, imzalanmayan uzun y,  imzalanmayan uzun, imzalanmamış uzun 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 və m2) + ((u >> 2)  m2); v = (v  m2) + ((v >> 2)  m2); x = x + y;  u = u + v;  x = (x  m3) + ((xx4)  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); x  0x000001FF qaytarır; }

Bir an üçün həyəcanlandım, ancaq gcc, -O3-ilə birbaşa fokuslar oynayırdı, amma bəzi testlərdə inline sözü istifadə etmirəm. Gcc oyunlarını oynamağa icazə verəndə, pop4 () üçün bir milyard çağırış 12.56 gigacle çəkir, amma qərara gəldim ki, bunlar daimi ifadələr kimi əyarlı argümanlardır. Daha realist sayda başqa 30% sürət qazanmaq üçün 19.6qc kimi görünür. Mənim test loop indi buna bənzəyir ki, hər bir arqument gcc'yi dayandırmaq üçün kifayət qədər fərqlidir.

hitime b4 = rdtsc (); (imzalanmayan uzun i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i)sum + = pop4 (i, i ^ 1, i, i | 1); hitime e4 = rdtsc (); 

8.17-də yekunlaşdırılan 256 milyard bit bitdi. Axtarış nəticələrini 16 bitə müqayisə edərək, 32 milyon bit üçün 1.02 saniyəyə qədər işləyir. Birbaşa müqayisə etmək mümkün deyil, çünki digər tezgahlarda bir saat tezliyi yoxdur, ancaq ilk növbədə L1 önbelleğinin fəlakətli istifadəsi olan 64 KB masadan siqaret çəkdiyim kimi görünür.

Yeniləmə: dörd daha çox xətt əlavə edərək açıq-aşkar etmək və pop6 () yaratmaq qərarına gəldik. 22.8 Hz-ə və 384 milyarda qədər bit 9.5 s-də yekunlaşdırılır. Yəni 20% -i artıq 32 milyard bit üçün 800 ms-dir.

28
03 окт. İstifadəçi tərəfindən verilmiş cavab 183351 03 oktyabr 2009-10-03 00:34 '09 at 0:34 2009-10-03 00:34

Niyə iterativ şəkildə 2 bölünmürsünüz?

 sayı = 0 n> 0 olduqda   əgər (n% 2) == 1 saymaq + = 1   n / = 2  

Mən bunu ən sürətli deyiləm, amma "ən yaxşı" bir qədər qeyri-müəyyəndir. Deyə bilərəm ki, "ən yaxşı" bir aydınlıq elementi olmalıdır

23
20 сент. cavab daniel 20 sep verilir . 2008-09-20 22:10 '08 saat 22:10 'da 2008-09-20 22:10

Hacker Delight bit-twiddling bit nümunələri yazarkən daha aydın olur.

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

Birinci addım ikili bitlərə hətta bitləri əlavə edir, ikisinin hər birində bir bit yaradır. Digər addımlar, bütün intu işğal edən yekun hesabı qazanana qədər, daha yüksək səviyyəli ardıcıllıqların alt hissəsinin parçaları əlavə edilərək, yığın ölçüsünü iki dəfə artırır.

19
20 дек. John Dimm tərəfindən verilmiş cavab 20 dekabr. 2013-12-20 09:55 '13 'da 9:55' da 2013-12-20 09:55

Axtarış paneli 2 32 arasında xoşbəxt bir mühit üçün və ayrıca hər bir bitlə yineleme:

 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 ünvanından

19
22 сент. cavab PhirePhly tərəfindən verilir Sep 22 2008-09-22 06:55 '08 saat 06:55 'da 2008-09-22 06:55

Bu ən sürətli ya da ən yaxşı həll deyil, amma mənimlə eyni sual tapdım və düşünməyə və düşünməyə başladı. наконец, я понял, что это можно сделать так, если вы получите проблему с математической стороны и нарисуете график, тогда вы обнаружите, что это функция, которая имеет некоторую периодическую часть, а затем вы понимаете разницу между периодами... так здесь вы идете:

 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); } } 
16
ответ дан Peter 19 окт. '12 в 15:31 2012-10-19 15:31

Это можно сделать в O(k) , где k - количество установленных битов.

 int NumberOfSetBits(int n) { int count = 0; while (n){ ++ count; n = (n - 1)  n; } return count; } 
15
ответ дан herohuyongtao 14 янв. '14 в 15:53 2014-01-14 15:53

Функция, которую вы ищете, часто называется "боковая сумма" или "подсчет количества" двоичного числа. Кнут обсуждает его в дофашике 1A, pp11-12 (хотя в томе 2, 4.6.3- (7) была краткая ссылка).

Локус classicus - статья Петра Вегнера "Техника подсчета в двоичном компьютере", из Связь ACM, том 3 (1960) Номер 5, стр. 322 . Он дает два разных алгоритма: один оптимизирован для чисел, которые, как ожидается, будут "разрежены" (т.е. Имеют небольшое количество единиц) и один для противоположного случая.

10
ответ дан Michael Dorfman 23 сент. '08 в 12:20 2008-09-23 12:20

Несколько открытых вопросов: -

  • Если число отрицательное, то?
  • Если число равно 1024, то метод "итеративно делить на 2" будет повторяться 10 раз.

мы можем модифицировать алгоритм для поддержки отрицательного числа следующим образом: -

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

теперь, чтобы преодолеть вторую проблему, мы можем написать algo как: -

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

для полной справки см.:

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

9
ответ дан Baban 07 мая '10 в 7:51 2010-05-07 07:51
9
ответ дан stacktay 08 нояб. '17 в 17:50 2017-11-08 17:50

Я думаю, что метод

8
ответ дан Erorr 01 июня '16 в 5:16 2016-06-01 05:16

Я использую приведенный ниже код, который более интуитивно понятен.

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

Логика: n и (n-1) сбрасывает последний бит набора из n.

PS: Я знаю, что это не O (1) решение, хотя и интересное решение.

8
ответ дан Manish Mulani 05 мая '12 в 10:12 2012-05-05 10:12

Что вы подразумеваете под "Лучшим алгоритмом"? Укороченный код или голодный код? Ваш код выглядит очень элегантно и имеет постоянное время выполнения. Код также очень короткий.

Но если скорость является основным фактором, а не размером кода, я думаю, что следующее может быть быстрее:

  static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... }; static int bitCountOfByte( int value ){ return BIT_COUNT[ value  0xFF ]; } static int bitCountOfInt( int value ){ return bitCountOfByte( value ) + bitCountOfByte( value >> 8 ) + bitCountOfByte( value >> 16 ) + bitCountOfByte( value >> 24 ); } 

Я думаю, что это будет не быстрее для 64-битного значения, но 32-разрядное значение может быть быстрее.

7
ответ дан Horcrux7 20 сент. '08 в 22:31 2008-09-20 22:31

если вы используете С++, другой вариант - использовать метапрограммирование шаблонов:

 // 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 only one bit left template<> int countBits<1>(int val) { return val  0x1; } 

:

 // to count bits in a byte/char (this returns 8) countBits<8>( 255 ) // another byte (this returns 7) countBits<8>( 254 ) // counting bits in a word/short (this returns 1) countBits<16>( 256 ) 

вы могли бы, конечно, расширить этот шаблон, чтобы использовать разные типы (даже для автоматического определения размера бит), но я сохранил его просто для ясности.

edit: забыл упомянуть, что это хорошо, потому что он должен работать в любом компиляторе С++, и он просто разворачивает ваш цикл для вас, если для подсчета бит используется постоянное значение (другими словами, Я уверен, что это самый быстрый общий метод, который вы найдете)

7
ответ дан pentaphobe 04 апр. '12 в 7:25 2012-04-04 07:25

Я написал быстрый битконтактный макрос для машин RISC примерно в 1990 году. Он не использует расширенную арифметику (умножение, деление,%), выборки памяти (слишком медленные), ветки (слишком медленные), но он предполагает, что CPU имеет 32-битный сдвиг ствола (другими словами, → 1 и → 32 занимают одинаковое количество циклов.) Он предполагает, что небольшие константы (такие как 6, 12, 24) ничего не стоят загружать в регистры, или хранятся во временных и повторных использования снова и снова.

С этими предположениями он рассчитан на 32 бита примерно на 16 циклов/инструкций на большинстве машин RISC. Обратите внимание, что 15 инструкций/циклов близки к нижней границе числа циклов или инструкций, потому что для сокращения количества слагаемых пополам требуется как минимум 3 команды (маска, сдвиг, оператор), поэтому log_2 (32) = 5, 5 x 3 = 15 инструкций является квазинизким.

 #define BitCount(X,Y) \ Y = X - ((X >> 1)  033333333333) - ((X >> 2)  011111111111); \ Y = ((Y + (Y >> 3))  030707070707); \ Y = (Y + (Y >> 6)); \ Y = (Y + (Y >> 12) + (Y >> 24))  077; 

Вот секрет первого и самого сложного шага:

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

поэтому, если взять первый столбец (A) выше, сдвинуть его вправо 1 бит и вычесть его из AB, я получаю вывод (CD). Расширение до 3 бит аналогично; вы можете проверить его с помощью 8-строчной логической таблицы, как показано выше, если хотите.

  • Дон Гиллис
7
ответ дан systemBuilder 12 июня '10 в 0:40 2010-06-12 00:40

Я всегда использую это в Конкурентном программировании, и это легко писать и эффективно:

 #include <bits/stdc++.h> using namespace std; int countOnes(int n) { bitset<32> b(n); return b.count(); } 
6
ответ дан diugalde 04 нояб. 2016-11-04 00:02 '16 'da 0:02 ' də 2016-11-04 00:02 'də

Java JDK1.5

Integer.bitCount(п);

где n - число, чье число должно подсчитываться.

проверьте также,

 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); } 
6
ответ дан Rahul 10 дек. '10 в 23:40 2010-12-10 23:40

Я особенно люблю этот пример из файла состояния:

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

Мне нравится, потому что это так красиво!

6
ответ дан Ross 23 сент. '08 в 4:29 2008-09-23 04:29

Я нашел реализацию подсчета бит в массиве с использованием команды SIMD (SSSE3 и AVX2). Он имеет производительность в 2-2,5 раза лучше, чем если бы он использовал встроенную функцию __popcnt64.

Версия SSSE3:

 #include <smmintrin.h> #include <stdint.h> const __m128i Z = _mm_set1_epi8(0x0); const __m128i F = _mm_set1_epi8(0xF); //Vector with pre-calculated bit count: const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); uint64_t BitCount(const uint8_t * src, size_t size) { __m128i _sum = _mm128_setzero_si128(); for (size_t i = 0; i < size; i += 16) { //load 16-byte vector __m128i _src = _mm_loadu_si128((__m128i*)(src + i)); //get low 4 bit for every byte in vector __m128i lo = _mm_and_si128(_src, F); //sum precalculated value from T _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo))); //get high 4 bit for every byte in vector __m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F); //sum precalculated value from T _sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi))); } uint64_t sum[2]; _mm_storeu_si128((__m128i*)sum, _sum); return sum[0] + sum[1]; } 

Версия AVX2:

 #include <immintrin.h> #include <stdint.h> const __m256i Z = _mm256_set1_epi8(0x0); const __m256i F = _mm256_set1_epi8(0xF); //Vector with pre-calculated bit count: const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4); uint64_t BitCount(const uint8_t * src, size_t size) { __m256i _sum = _mm256_setzero_si256(); for (size_t i = 0; i < size; i += 32) { //load 32-byte vector __m256i _src = _mm256_loadu_si256((__m256i*)(src + i)); //get low 4 bit for every byte in vector __m256i lo = _mm256_and_si256(_src, F); //sum precalculated value from T _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo))); //get high 4 bit for every byte in vector __m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F); //sum precalculated value from T _sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi))); } uint64_t sum[4]; _mm256_storeu_si256((__m256i*)sum, _sum); return sum[0] + sum[1] + sum[2] + sum[3]; } 
6
ответ дан ErmIg 15 февр. '16 в 17:33 2016-02-15 17:33

Существует множество алгоритмов для подсчета установленных битов; но я думаю, что лучший из них самый быстрый! Вы можете увидеть подробную информацию на этой странице:

Бит Twiddling Hacks

Aşağıdakıları təklif edirəm:

Счетные биты, установленные в 14, 24 или 32-битных словах с использованием 64-разрядных инструкций

 unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v // option 1, for at most 14-bit values in v: c = (v * 0x200040008001ULL  0x111111111111111ULL) % 0xf; // option 2, for at most 24-bit values in v: c = ((v  0xfff) * 0x1001001001001ULL  0x84210842108421ULL) % 0x1f; c += (((v  0xfff000) >> 12) * 0x1001001001001ULL  0x84210842108421ULL) % 0x1f; // option 3, for at most 32-bit values in v: c = ((v  0xfff) * 0x1001001001001ULL  0x84210842108421ULL) % 0x1f; c += (((v  0xfff000) >> 12) * 0x1001001001001ULL  0x84210842108421ULL) % 0x1f; c += ((v >> 24) * 0x1001001001001ULL  0x84210842108421ULL) % 0x1f; 

Для этого метода требуется 64-разрядный процессор с быстрым модулем. Первый вариант принимает только 3 операции; второй вариант занимает 10; и третий вариант занимает 15.

5
ответ дан Mostafa 13 апр. '11 в 10:50 2011-04-13 10:50

Вот портативный модуль (ANSI-C), который может сравнивать каждый из ваших алгоритмов с любой архитектурой.

В вашем процессоре есть 9-битные байты? Нет проблем:-) На данный момент он реализует 2 алгоритма, алгоритм K R и байтную таблицу поиска. Таблица поиска в среднем в 3 раза быстрее, чем алгоритм K R. Если кто-то может понять способ превратить алгоритм "Хакерский восторг", не стесняйтесь его добавлять.

 #ifndef _BITCOUNT_H_ #define _BITCOUNT_H_  int bitcount( unsigned int );  enum strategy { onTheFly, lookupTable, strategyCount };  extern const char *strategyNames[];  void setStrategy( enum strategy ); #endif 

.

 #include <limits.h> #include "bitcount.h"  static unsigned char _bitCountTable[UCHAR_MAX + 1]; static unsigned int _lookupTableInitialized = 0; static int _defaultBitCount( unsigned int val ) { int count;  for ( count = 0; val; ++count ) val  val - 1; return count; }  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; } }  int bitcount( unsigned int val ) { return _bitcount( val ); } #ifdef _BITCOUNT_EXE_ #include <stdio.h> #include <stdlib.h> #include <time.h>  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",  ) == EOF ) break; switch ( option ) { case 1: printf( "Please enter the integer: " ); if ( scanf( "%d",  ) != 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",  ) != EOF ) benchmark( option ); break; case 3: goto EXIT; break; default: printf( "Invalid option\n" ); } } EXIT: printf( "\n" ); return 0; } #endif 
5
ответ дан Robert S. Barnes 29 марта '11 в 11:04 2011-03-29 11:04

Быстрое решение С# с использованием предварительно вычисленной таблицы байт-бит с разветвлением по размеру ввода.

 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 }; } 
4
ответ дан dadhi 30 янв. '14 в 14:32 2014-01-30 14:32

32-бит или нет? Я просто пришел с этим методом в Java после прочтения " взломать интервью по кодированию " 4-е издание упражнений 5.5 (глава 5: Бит-манипуляция). Если младший значащий бит равен 1 приращению count , тогда сдвиньте правое целое число.

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

Я думаю, что это более интуитивно, чем решения с постоянным 0x33333333, независимо от того, насколько они быстры. Это зависит от вашего определения "лучший алгоритм".

4
ответ дан Raymond Chenon 16 нояб. '11 в 2:52 2011-11-16 02:52
  • 1
  • 2

Другие вопросы по меткам или Задайте вопрос