Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Aikaa on 6.1. saakka.

Koodivinkit: C: Laske bitit

Kirjoittaja: kala

Kirjoitettu: 12.06.2003 – 19.02.2012

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

Kommentit

FooBat [04.02.2019 23:01:20]

Lainaa #

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

Kirjoita kommentti

Muista lukea kirjoitusohjeet.
Tietoa sivustosta