Kirjautuminen
Tehtävät
Kilpailu
Putka Open 2020 -kisan
2. kierros: 25.–27.9.
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;
}Tämä on vähän vanha vinkki, mutta jos on mielenkiintoa bittikikkailuun kannattaa lukaista helmiä täältä: https://graphics.stanford.edu/~seander/bithacks.
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ä).