Keskustelu: Koodit: C: Laske bitit

Tällä funktiolla voit laskea, montako ykkösbittiä 32-bittisessä kokonaisluvussa on.

int count_bits(unsigned long i)
{
      i = ((i & 0xAAAAAAAAUL) >>  1) + (i & 0x55555555UL);
      i = ((i & 0xCCCCCCCCUL) >>  2) + (i & 0x33333333UL);
      i = ((i & 0xF0F0F0F0UL) >>  4) + (i & 0x0F0F0F0FUL);
      i = ((i & 0xFF00FF00UL) >>  8) + (i & 0x00FF00FFUL);
      i = ((i & 0xFFFF0000UL) >> 16) + (i & 0x0000FFFFUL);
      return (int)i;
}

Tämä on vähän vanha vinkki, mutta jos on mielenkiintoa bittikikkailuun kannattaa lukaista helmiä täältä: https://graphics.stanford.edu/~seander/bithacks.html

Tuolla esimerkiksi on tuon ykkösbittien laskennan 'optimoitu' versio.

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
...
v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Ja sitten tietenkin, jos tällä on oikeasti tarvetta nopeuteen, kannattaa käyttää tutustua kääntäjä spesifisiin intirinsic käskyihin kuten Microsoftilla __popcnt ja __builtin_popcount clang/gcc.

Kannattaa tutustua myös https://godbolt.org/ sivustoon, jolla voi testailla helposti minkälaista konekoodia kirjoittamasi koodi tuottaa. Esim. on jännä havaita, että clang ainakin tietyillä asetuksilla tuottaa __builtin_popcount käskyllä tuon saman koodin joka on tuossa ylempänä esitetty. Toisaalta tuon saanee tuottamaan myös sen yksittäisen popcnt konekäskyn, jos kääntäjälle antaa oikeat parametrit (ja sanoo, että laite tukee käskyä).

Jos oletetaan että bittejä on vähän, niin myös tällainen toimii suht nopeasti lähtökohtaisesti minkä vaan kokoiselle kokonaisluvulle.

int popCount (U64 x) {
   int count = 0;
   while (x) {
       count++;
       x &= x - 1;
   }
   return count;
}

Tuo Grezin toteutus on hyvä myös siksi, että kääntäjät osaavat korvata sen popcnt:lla jos se on käytössä: https://godbolt.org/z/cMzn4v