it-swarm-eu.dev

Jak spočítat počet nastavených bitů v 32bitovém celém čísle?

8 bitů reprezentujících číslo 7 vypadá takto:

00000111

Jsou nastaveny tři bity. 

Jaké jsou algoritmy pro určení počtu nastavených bitů v 32bitovém celém čísle?

795
Matt Howells

Toto je znáno jak ' Hamming váha ', 'popcount' nebo 'postranní sčítání'.

'Nejlepší' algoritmus opravdu záleží na tom, na kterém procesoru se právě nacházíte a jaký je váš vzor použití.

Některé CPU mají jeden vestavěný instrukce dělat to a jiní mají paralelní instrukce, které jednají na bitových vektorech. Paralelní instrukce (jako xpopcnt, na procesorech, kde je podporováno) budou téměř jistě nejrychlejší. Některé jiné architektury mohou mít pomalou instrukci implementovanou s mikrokódovanou smyčkou, která testuje trochu za cyklus (citace potřebná).

Metoda vyhledávání předem obsazené tabulky může být velmi rychlá, pokud má váš procesor velkou mezipaměť a/nebo děláte spoustu těchto instrukcí v těsné smyčce. Může však trpět kvůli nákladu „mezipaměti“, kde CPU musí přivést část tabulky z hlavní paměti.

Pokud víte, že vaše bajty budou většinou 0 nebo většinou 1, pak pro tyto scénáře existují velmi účinné algoritmy.

Věřím, že velmi dobrý algoritmus pro obecné účely je následující, známý jako „paralelní“ nebo „variabilní přesný SWAR algoritmus“. Vyjádřil jsem to v pseudo jazyce typu C, možná budete muset upravit, aby fungoval pro určitý jazyk (např. Pomocí uint32_t pro C++ a >>> v Javě):

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

To má nejlepší nejhorší chování některého z diskutovaných algoritmů, takže bude efektivně řešit jakýkoli vzor použití nebo hodnoty, které na něj hodíte.


Tento bitový SWAR algoritmus by mohl být paralelizován, aby mohl být proveden ve více vektorových prvcích najednou, namísto v jediném celočíselném registru, pro zrychlení CPU s SIMD, ale ne použitelnou popcount instrukcí. (např. x86-64 kód, který musí běžet na jakémkoliv CPU, ne jen Nehalem nebo později.)

Nejlepším způsobem použití vektorových instrukcí pro popcount je však obvykle použití proměnné shuffle pro vyhledávání tabulky pro 4 bity v čase každého bajtu paralelně. (4 bity indexují 16 vstupní tabulku uchovávanou ve vektorovém registru).

Na procesorech Intel může 64bitová instrukce hardwaru překonat hodnotu SSSE3 PSHUFB bit-paralelní implementace přibližně o faktor 2, ale pouze pokud ji kompilátor dostane správně . Jinak SSE může vyrazit výrazně dopředu. Novější verze kompilátoru jsou si vědomy popcnt falešné závislostiproblém na Intel .

Reference:

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)

800
Matt Howells

Také zvážit vestavěné funkce vašich kompilátorů.

Na kompilátoru GNU můžete například použít pouze:

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

V nejhorším případě kompilátor vygeneruje volání funkce. V nejlepším případě kompilátor vydá instrukci cpu, která provede stejnou práci rychleji.

Integrace GCC dokonce funguje na více platformách. Popcount se stane mainstreamem v architektuře x86, takže je smysluplné začít používat vnitřní. Jiné architektury mají popcount roky.


Na x86 můžete kompilátoru říci, že může převzít podporu pro popcnt instrukci s -mpopcnt nebo -msse4.2 a také povolit vektorové instrukce, které byly přidány ve stejné generaci. Viz Možnosti GCC x86 . -march=nehalem (nebo -march= cokoliv, co chcete, aby váš kód převzal a naladit), by mohlo být dobrou volbou. Spuštění výsledného binárního kódu na starším procesoru bude mít za následek chybu ilegální instrukce.

Pro optimalizaci binárních souborů pro počítač, na kterém je stavíte, použijte -march=native (pomocí gcc, clang nebo ICC).

MSVC poskytuje vlastní instrukci x86 popcnt , ale na rozdíl od gcc je to skutečně pro hardwarovou instrukci a vyžaduje podporu hardwaru.


Použití std::bitset<>::count() namísto vestavěné

Teoreticky by každý kompilátor, který umí efektivně vydělávat pro cílový procesor, měl tuto funkci vystavit prostřednictvím ISO C++ std::bitset<> . V praxi můžete být s některými cílovými CPU lépe v režimu bit-hack AND/shift/ADD.

Pro cílové architektury, kde je popcount hardwaru volitelné rozšíření (jako x86), ne všechny kompilátory mají std::bitset, které ho využívá, když je k dispozici. Například MSVC nemá žádný způsob, jak povolit podporu popcnt v době kompilace a vždy používá vyhledávání v tabulce , dokonce s /Ox /Arch:AVX (což znamená, že SSE4.2, i když technicky existuje samostatný bit funkce pro popcnt.)

Ale přinejmenším dostanete něco přenosného, ​​který funguje všude, a s gcc/clang se správnými cílovými možnostmi získáte hardware popcount pro architektury, které ho podporují.

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

Viz asm z gcc, clang, icc a MSVC na kompilátoru Godbolt.

x86-64 gcc -O3 -std=gnu++11 -mpopcnt vydává toto:

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 (pro verzi int arg):

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

Tento zdroj není specifický pro x86 nebo GNU specifický, ale pouze pro x86 kompilace s gcc/clang/icc.

Všimněte si také, že gcc pro architektury bez popcountu s jednou instrukcí je vyhledáváním v byte-at-a-time. To není skvělé pro ARM, například .

198
Nils Pipenbrinck

Podle mého názoru je "nejlepším" řešením ten, který může číst jiný programátor (nebo původní programátor o dva roky později), aniž by se o tom zmínil. Můžete také chtít nejrychlejší nebo nejchytřejší řešení, které již někteří poskytli, ale kdykoliv preferuji čitelnost.

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

Pokud chcete více rychlosti (a za předpokladu, že je dokumentujete dobře, abyste pomohli svým nástupcům), můžete použít vyhledávání v tabulce:

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

I když se spoléhají na konkrétní velikosti datových typů, takže nejsou přenosné. Vzhledem k tomu, že mnohé optimalizace výkonu nejsou stejně přenosné, nemusí to být problém. Pokud chcete přenositelnost, držím se čitelného řešení.

172
paxdiablo

Z Hackerova potěšení, s. 66, obr. 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;
}

Provede příkaz ~ 20-ish (Arch dependent), bez větvení.

Hacker Delightje nádherné! Vysoce doporučeno.

95
Kevin Little

Myslím, že nejrychlejší cesta - bez použití vyhledávacích tabulek a popcount - je následující. Počítá nastavené bity pouze s 12 operacemi.

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

Funguje to proto, že můžete spočítat celkový počet nastavených bitů dělením na dvě poloviny, počítáním počtu nastavených bitů v obou polovinách a jejich přidáním. Také známý jako Divide and Conquer paradigma. Pojďme se dostat do detailu. 

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

Počet bitů ve dvou bitech může být 0b00, 0b01 nebo 0b10. Zkuste to zkusit na 2 bitech. 

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

To je to, co bylo požadováno: poslední sloupec zobrazuje počet nastavených bitů v každém dvou bitovém páru. Pokud je číslo dvou bitů >= 2 (0b10), pak and vytvoří 0b01, jinak vytvoří 0b00

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

Toto prohlášení by mělo být snadno pochopitelné. Po první operaci máme počet nastavených bitů v každém ze dvou bitů, nyní spočítáme počet v každém 4 bitu.

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

Následně shrneme výše uvedený výsledek, což nám dává celkový počet nastavených bitů ve 4 bitech. Poslední prohlášení je nejsložitější.

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

Pojďme to rozdělit ... 

v + (v >> 4)

Je to podobné druhému tvrzení; místo toho počítáme nastavené bity ve skupinách po 4. Víme - díky našim předchozím operacím - že každý hrobek má v sobě počet nastavených bitů. Podívejme se na příklad. Předpokládejme, že máme bajt 0b01000010. To znamená, že první nibble má svůj 4bitový set a druhý má 2bits. Teď přidáme ty křupky dohromady. 

0b01000010 + 0b01000000

To nám dává počet nastavených bitů v byte, v první nibble 0b01100010 a proto zakryjeme poslední čtyři bajty všech bytů v čísle (jejich vyřazení).

0b01100010 & 0xF0 = 0b01100000

Každý bajt má v sobě počet nastavených bitů. Musíme je přidat dohromady. Trik je násobit výsledek 0b10101010 který má zajímavou vlastnost. Pokud má naše číslo čtyři bajty, A B C D, bude to mít za následek nové číslo s těmito bajty A+B+C+D B+C+D C+D D. 4bajtové číslo může mít maximálně 32 bitů, které mohou být reprezentovány jako 0b00100000.

Vše, co nyní potřebujeme, je první bajt, který má součet všech nastavených bitů ve všech bajtech, a my jej dostaneme >> 24. Tento algoritmus byl navržen pro slova 32 bit, ale může být snadno upraven pro slova 64 bit.

73
vidit

Pokud používáte Javu, zabudovaná metoda Integer.bitCount to udělá.

54
Noether

Nudil jsem se a načasoval tři iterace tří přístupů. Kompilátor je gcc -O3. CPU je to, co dali do 1. gen Macbook Pro.

Nejrychlejší je následující: 3,7 sekundy:

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

Druhé místo jde do stejného kódu, ale dívá se na 4 bajty namísto 2 polovičních slov. To trvalo přibližně 5,5 sekundy.

Třetí místo je přístup bit-twiddling „sideways“, který trval 8,6 sekundy.

Čtvrté místo jde do __builtin_popcount () GCC v hanebných 11 vteřinách.

Přístup, který počítal jeden bit v čase, byl pomalejší a já jsem se nudil, když jsem čekal na jeho dokončení.

Takže pokud vám záleží na výkonu nad všemi ostatní pak použít první přístup. Pokud vám záleží, ale ne dost na to, abyste na to utratili 64Kb RAM, použijte druhý přístup. V opačném případě použijte čitelný (ale pomalý) přístup s jedním bitem v čase.

Je těžké si představit situaci, kdy byste chtěli použít bit-twiddling přístup.

Upravit: Podobné výsledky zde .

53
Mike F
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;
}

Dovolte mi vysvětlit tento algoritmus.

Tento algoritmus je založen na algoritmu Divide a Conquer. Předpokládejme, že existuje 8bitové celé číslo 213 (11010101 v binárním režimu), algoritmus funguje takto (pokaždé sloučení dvou sousedních bloků):

+-------------------------------+
| 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
abcdabcd987

This is one of those questions where it helps to know your micro-architecture. I just timed two variants under gcc 4.3.3 compiled with -O3 using C++ inlines to eliminate function call overhead, one billion iterations, keeping the running sum of all counts to ensure the compiler doesn't remove anything important, using rdtsc for timing (clock cycle precise).

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

The unmodified Hacker's Delight took 12.2 gigacycles. My parallel version (counting twice as many bits) runs in 13.0 gigacycles. 10.5s total elapsed for both together on a 2.4GHz Core Duo. 25 gigacycles = just over 10 seconds at this clock frequency, so I'm confident my timings are right.

This has to do with instruction dependency chains, which are very bad for this algorithm. I could nearly double the speed again by using a pair of 64-bit registers. In fact, if I was clever and added x+y a little sooner I could shave off some shifts. The 64-bit version with some small tweaks would come out about even, but count twice as many bits again.

With 128 bit SIMD registers, yet another factor of two, and the SSE instruction sets often have clever short-cuts, too.

There's no reason for the code to be especially transparent. The interface is simple, the algorithm can be referenced on-line in many places, and it's amenable to comprehensive unit test. The programmer who stumbles upon it might even learn something. These bit operations are extremely natural at the machine level.

OK, I decided to bench the tweaked 64-bit version. For this one sizeof(unsigned long) == 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;
}

That looks about right (I'm not testing carefully, though). Now the timings come out at 10.70 gigacycles / 14.1 gigacycles. That later number summed 128 billion bits and corresponds to 5.9s elapsed on this machine. The non-parallel version speeds up a tiny bit because I'm running in 64-bit mode and it likes 64-bit registers slightly better than 32-bit registers.

Let's see if there's a bit more OOO pipelining to be had here. This was a bit more involved, so I actually tested a bit. Each term alone sums to 64, all combined sum to 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;
}

I was excited for a moment, but it turns out gcc is playing inline tricks with -O3 even though I'm not using the inline keyword in some tests. When I let gcc play tricks, a billion calls to pop4() takes 12.56 gigacycles, but I determined it was folding arguments as constant expressions. A more realistic number appears to be 19.6gc for another 30% speed-up. My test loop now looks like this, making sure each argument is different enough to stop gcc from playing tricks.

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

256 billion bits summed in 8.17s elapsed. Works out to 1.02s for 32 million bits as benchmarked in the 16-bit table lookup. Can't compare directly, because the other bench doesn't give a clock speed, but looks like I've slapped the snot out of the 64KB table edition, which is a tragic use of L1 cache in the first place.

Update: decided to do the obvious and create pop6() by adding four more duplicated lines. Came out to 22.8gc, 384 billion bits summed in 9.5s elapsed. So there's another 20% Now at 800ms for 32 billion bits.

28
user183351

Proč ne iterativně dělí 2?

 počet = 0 
, zatímco n> 0 
 pokud (n% 2) == 1 
 počet + = 1 
 n/= 2 

Souhlasím, že to není nejrychlejší, ale "nejlepší" je poněkud nejednoznačný. Řekl bych, že "nejlepší" by měl mít prvek jasnosti

25
daniel

Hackerova potěšení bit-twiddling se stává mnohem jasnější, když vypíšete bitové vzory. 

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

První krok přidává sudé bity k lichým bitům a vytváří součet bitů v každé ze dvou bitů. Ostatní kroky přidávají kusy s nízkým řádem kusy s vysokým řádem a zdvojnásobí velikost kusu až nahoru, až budeme mít konečný počet, který by zabral celý int.

20
John Dimm

Pro šťastné médium mezi 232 vyhledávací tabulka a iterace jednotlivých bitů jednotlivě:

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

Z http://ctips.pbwiki.com/CountBits

19
PhirePhly

Není to nejrychlejší nebo nejlepší řešení, ale našel jsem stejnou otázku v cestě a začal jsem přemýšlet a přemýšlet. konečně jsem si uvědomil, že to lze udělat takhle, pokud dostanete problém z matematické strany, a nakreslete graf, pak zjistíte, že je to funkce, která má nějakou periodickou část, a pak si uvědomíte rozdíl mezi obdobími ... takže tady máš:

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

To lze provést v O(k), kde k je počet nastavených bitů.

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

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

    return count;
}
16
herohuyongtao

Funkce, kterou hledáte, se často nazývá "bokem" nebo "počtem obyvatel" binárního čísla. Knuth to diskutuje v pre-Fascicle 1A, pp11-12 (ačkoli ve svazku 2, 4.6.3- (7).)

Locus classicusje článek Petera Wegnera "Technika pro počítání v binárním počítači" z komunikace ACM, svazek 3 (1960) číslo 5, strana 322 . Uvádí zde dva různé algoritmy, jeden optimalizovaný pro čísla, u nichž se očekává, že budou "řídké" (tj. Mají malý počet) a jeden pro opačný případ.

10
Michael Dorfman
  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;
    }
9
stacktay

Několik otevřených otázek: -

  1. Pokud je číslo záporné?
  2. Pokud je číslo 1024, pak bude metoda "iterativně dělit 2" iterovat 10krát.

algo můžeme modifikovat tak, aby podporovalo záporné číslo následujícím způsobem: -

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

teď k překonání druhého problému můžeme napsat algo jako: -

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

pro kompletní reference viz:

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

9
Baban

Používám níže uvedený kód, který je intuitivnější.

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

Logika: n & (n-1) vynuluje poslední nastavený bit n.

P.S: Vím, že to není O(1) řešení, i když je to zajímavé řešení.

8
Manish Mulani

Myslím, že metoda Brian Kernighan bude také užitečná ... Prochází tolika iteracemi, jakými jsou nastavené bity. Pokud tedy máme 32bitové slovo pouze s nastaveným vysokým bitem, pak to bude jen jednou projít smyčkou. 

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

Publikoval v roce 1988, C programovací jazyk 2. vydání. (Brian W. Kernighan a Dennis M. Ritchie) uvádí toto ve cvičení 2-9. 19. dubna 2006 Don Knuth poukázal na mě, že tato metoda "byla poprvé publikována Peterem Wegnerem v CACM 3 (1960), 322. (Také objevil nezávisle Derrick Lehmer a publikoval v roce 1964 v knize upravované Beckenbachem.)"

8
Erorr

Co znamená "nejlepší algoritmus"? Zkrácený kód nebo kód nalačno? Váš kód vypadá velmi elegantně a má konstantní dobu provedení. Kód je také velmi krátký.

Ale pokud je rychlost hlavním faktorem a ne velikostí kódu, pak myslím, že následování může být rychlejší:

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

Myslím, že pro 64bitovou hodnotu to nebude rychlejší, ale 32bitová hodnota může být rychlejší.

7
Horcrux7

pokud používáte C++, další možností je použít metaprogramování šablony:

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

použití by bylo:

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

můžete samozřejmě dále rozšířit tuto šablonu pro použití různých typů (i auto-detekce bit velikost), ale já jsem udržel to jednoduché pro přehlednost.

edit: zapomněl jsem to zmínit, je to dobré, protože to should práce v libovolném kompilátoru C++ a to v podstatě jen rozbalí vaši smyčku pro vás, pokud je pro počítání bitů použita konstantní hodnota (jinými slovy, Jsem si jistý, že je to nejrychlejší obecná metoda, kterou najdete)

7
pentaphobe

Napsal jsem rychlé bitcountové makro pro RISC stroje asi v roce 1990. Nepoužívá pokročilé aritmetické (násobení, dělení,%), paměťové vzestupy (příliš pomalé), větve (příliš pomalé), ale předpokládá, že CPU má 32-bitový barrel shifter (jinými slovy, >> 1 a >> 32 zabírá stejné množství cyklů.) Předpokládá se, že malé konstanty (jako 6, 12, 24) nic nezatěžují načtením do registrů, nebo jsou uloženy v provizorních časech a znovu a znovu.

S těmito předpoklady počítá 32 bitů v přibližně 16 cyklech/instrukcích na většině strojů RISC. Všimněte si, že 15 instrukcí/cyklů se blíží dolní hranici počtu cyklů nebo instrukcí, protože se zdá, že trvá minimálně 3 instrukce (maska, posun, operátor) ke snížení počtu přidaných položek na polovinu, takže log_2 (32) = 5, 5 x 3 = 15 instrukcí je kvazi-dolní.

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

Zde je tajemství prvního a nejsložitějšího kroku:

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

takže pokud vezmu první sloupec (A) výše, posuňte ho doprava 1 bit a odečtěte jej od AB, dostanu výstup (CD). Rozšíření na 3 bity je podobné; můžete ho zkontrolovat s 8-řádkovým boolean tabulkou, jako je moje výše, pokud si budete přát.

  • Don Gillies
7
systemBuilder

Toto vždy používám v programu Competitive Programming a je snadné jej psát a efektivně:

#include <bits/stdc++.h>

using namespace std;

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

Našel jsem implementaci bitového počítání v poli s využitím instrukce SIMD (SSSE3 a AVX2). Má 2-2,5krát vyšší výkon, než kdyby používal vlastní funkci __popcnt64.

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

Verze 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

Jsem obzvláště rád tohoto příkladu ze souboru štěstí:

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

Líbí se mi to nejlepší, protože je to tak hezké!

6
Ross

Java JDK1.5

Integer.bitCount (n);

kde n je číslo, jehož 1 má být započítáno.

zkontrolovat také,

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

Zde je přenosný modul (ANSI-C), který dokáže porovnat každý z vašich algoritmů na libovolné architektuře. 

Váš procesor má 9 bitových bytů? Žádný problém :-) Momentálně implementuje 2 algoritmy, algoritmus K&R a vyhledávací tabulku bajtů. Vyhledávací tabulka je v průměru 3krát rychlejší než algoritmus K&R. Pokud někdo může najít způsob, jak "Hacker Delight" algoritmus přenosný neváhejte přidat.

#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
5
Robert S. Barnes

Existuje mnoho algoritmů pro počítání nastavených bitů; ale myslím, že nejlepší z nich je rychlejší! Na této stránce můžete vidět podrobné informace:

Bit Twiddling Hacks

Navrhuji tento:

Počítání bitů nastavených v 14, 24 nebo 32bitových slovech pomocí 64bitových instrukcí

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;

Tato metoda vyžaduje, aby 64bitový procesor s rychlým modulem modulace byl účinný. První možnost je pouze 3 operace; druhá možnost trvá 10; a třetí možnost trvá 15. 

5
Mostafa

Rychlé řešení C # s použitím předem vypočtené tabulky bajtů bitů s větvením na vstupní velikosti.

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

32-bit nebo ne? Právě jsem přišel s touto metodou v Javě po přečtení " praskání kódovacího rozhovoru " cvičení 4. vydání 5.5 (kap 5: Bit Manipulation). Pokud je nejméně významný bit 1 přírůstek count, pak celé číslo posunete doprava.

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

Myslím, že tohle je více intuitivní než řešení s konstantní 0x33333333 bez ohledu na to, jak rychle jsou. Záleží na vaší definici "nejlepšího algoritmu".

4
Raymond Chenon

co můžete udělat, je 

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

logika za tímto je bity n-1 je invertován od nejvíce nastaveného bitu n. jestliže n = 6 tj 110 pak 5 je 101 bity jsou invertovány od nejvíce nastaveného bitu n takže pokud my & tito dva uděláme pravý bit 0 v každé iteraci a vždy jdeme na nejbližší bit nastavený napravo. Proto počítáme nastavený bit. Nejhorší časová složitost bude O(logn), když je nastaven každý bit.

3
Varun Gusain

Osobně používám toto:

  public static int myBitCount(long L){
      int count = 0;
      while (L != 0) {
         count++;
         L ^= L & -L; 
      }
      return count;
  }
2
SteveR
int bitcount(unsigned int n)
{ 
      int count=0;
      while(n)
      {
           count += n & 0x1u;
           n >>= 1;
      }
      return  count;
 }

Iterovaný 'počet' běží v čase úměrném celkovému počtu bitů. To prostě smyčky přes všechny bity, končit mírně dříve, protože podmínka, zatímco. Užitečné, jestliže 1'S nebo nastavené bity jsou řídké a mezi nejméně významnými bity .

1
Mufaddal Kagda

Další Hammingův váhový algoritmus, pokud jste na CPU schopném BMI2

the_weight=__tzcnt_u64(~_pext_u64(data[i],data[i]));

Bavte se!

1
Anders Cedronius

Můžete použít vestavěnou funkci s názvem __builtin_popcount (). V C++ je no__builtin_popcount, ale je to vestavěná funkce kompilátoru GCC. Tato funkce vrátí počet nastavených bitů v celém čísle.

int __builtin_popcount (unsigned int x);

Odkaz: Bit Twiddling Hacks

1
rashedcs
int countBits(int x)
{
    int n = 0;
    if (x) do n++;
           while(x=x&(x-1));
    return n;
}   

Nebo také:

int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
1
abelenky

V jazyce Java 8 nebo 9 vyvolejte pouze Integer.bitCount.

1

Zde je řešení, které dosud nebylo zmíněno s využitím bitfieldů. Následující program počítá nastavené bity v poli 100000000 16bitových celých čísel pomocí 4 různých metod. Výsledky časování jsou uvedeny v závorkách (na MacOSX, s gcc -O3):

#include <stdio.h>
#include <stdlib.h>

#define LENGTH 100000000

typedef struct {
    unsigned char bit0 : 1;
    unsigned char bit1 : 1;
    unsigned char bit2 : 1;
    unsigned char bit3 : 1;
    unsigned char bit4 : 1;
    unsigned char bit5 : 1;
    unsigned char bit6 : 1;
    unsigned char bit7 : 1;
} bits;

unsigned char sum_bits(const unsigned char x) {
    const bits *b = (const bits*) &x;
    return b->bit0 + b->bit1 + b->bit2 + b->bit3 \
         + b->bit4 + b->bit5 + b->bit6 + b->bit7;
}

int NumberOfSetBits(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

#define out(s) \
    printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);

int main(int argc, char **argv) {
    unsigned long i, s;
    unsigned short *x = malloc(LENGTH*sizeof(short));
    unsigned char lut[65536], *p;
    unsigned short *ps;
    int *pi;

    /* set 3/4 of the bits */
    for (i=0; i<LENGTH; ++i)
        x[i] = 0xFFF0;

    /* sum_bits (1.772s) */
    for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));
    out(s);

    /* NumberOfSetBits (0.404s) */
    for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));
    out(s);

    /* populate lookup table */
    for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)
        lut[i] = sum_bits(p[0]) + sum_bits(p[1]);

    /* 256-bytes lookup table (0.317s) */
    for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);
    out(s);

    /* 65536-bytes lookup table (0.250s) */
    for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);
    out(s);

    free(x);
    return 0;
}

Zatímco verze bitfieldu je velmi čitelná, výsledky časování ukazují, že je více než 4x pomalejší než NumberOfSetBits(). Implementace založené na vyhledávací tabulce jsou stále ještě o něco rychlejší, zejména s tabulkou 65 kB.

1
Stefan

Zde je ukázkový kód, který může být užitečný.

private static final int[] bitCountArr = new int[]{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};
private static final int firstByteFF = 255;
public static final int getCountOfSetBits(int value){
    int count = 0;
    for(int i=0;i<4;i++){
        if(value == 0) break;
        count += bitCountArr[value & firstByteFF];
        value >>>= 8;
    }
    return count;
}
0
#!/user/local/bin/Perl


    $c=0x11BBBBAB;
     $count=0;
     $m=0x00000001;
    for($i=0;$i<32;$i++)
    {
        $f=$c & $m;
        if($f == 1)
        {
            $count++;
        }
        $c=$c >> 1;
    }
    printf("%d",$count);

ive done it through a Perl script. the number taken is $c=0x11BBBBAB   
B=3 1s   
A=2 1s   
so in total  
1+1+3+3+3+2+3+3=19
0
dhpant28

Tento přístup jsem nikde neviděl:

int nbits(unsigned char v) {
    return ((((v - ((v >> 1) & 0x55)) * 0x1010101) & 0x30c00c03) * 0x10040041) >> 0x1c;
}

Funguje na bajt, takže by musel být volán čtyřikrát pro 32bitové celé číslo. Je odvozen z bočního sčítání, ale používá dva 32-bitové násobení ke snížení počtu instrukcí pouze na 7.

Většina současných kompilátorů C optimalizuje tuto funkci pomocí instrukcí SIMD (SSE2), když je jasné, že počet požadavků je násobkem 4, a stává se poměrně konkurenceschopným. Je přenosný, může být definován jako makro nebo inline funkce a nepotřebuje datové tabulky.

Tento přístup může být rozšířen na práci na 16 bitech najednou s použitím 64bitových násobení. Nepodaří se však, když je nastaveno všech 16 bitů, vrací nulu, takže jej lze použít pouze v případě, že vstupní hodnota 0xffff není k dispozici. Je také pomalejší díky 64bitovým operacím a není optimálně optimalizován.

0
cipilo

Co takhle převést celé číslo na binární řetězec a spočítat ty?

php řešení:

substr_count( decbin($integer), '1' );
0
KeineKaefer

Jednoduchý algoritmus pro výpočet počtu nastavených bitů:

int countbits(n){
     int count = 0;
     while(n != 0){
        n = n & (n-1);
        count++;
   }
   return count;
}

Vezměme příklad 11 (1011) a zkuste ručně spustit algoritmus. Měl by vám hodně pomoci!

0
Arjun Singh

Jednoduchý způsob, který by měl fungovat pěkně pro malé množství bitů něco takového (pro 4 bity v tomto příkladu):

(i & 1) + (i & 2)/2 + (i & 4)/4 + (i & 8)/8

Mohli by to jiní doporučit pro malý počet bitů jako jednoduché řešení?

0