Den speciella instruktionen i frÄga Àr instruktionen POPCNT. (Sök efter 4-395 i denna PDF.) Detta Àr alltsÄ en hÄrdvaruinstruktion som rÀknar antalet bitar som Àr satta i en variabel i en enda instruktion. Rykten sÀger att det var NSA som bestÀllt att denna instruktion, och den Àr bl.a. anvÀndbar för kryptografi. Mer finns att lÀsa hÀr: https://vaibhavsagar.com/blog/2019/09/08/popcount/
Det finns lite olika sÀtt att se till att anropa denna funktion, och jag lekte och lÀrde mig en del om inline-ASM, men kom fram till att det bÀsta sÀttet var att anvÀnda GCC:s inbyggda funktion __builtin_popcount för detta. DÄ bör den nÀmligen bli portabel till andra processorer (bl.a. finns Àven en liknande instruktion pÄ ARM), Àven processorer som saknar POPCNT. För att faktiskt generera POPCNT-instruktionerna sÄ mÄste man kompilera med flaggan -mpopcnt i GCC, annars genereras bara en trÄkig loop för detta istÀllet.
Varför Àr denna instruktion sÀrskilt intressant för denna dags pussel? Jo, lÄt mig förklara!
Pusslet gÄr ut pÄ att man ska gÄ igenom ett antal gruppers ja/nej-svar. Man ska rÀkna ut hur mÄnga frÄgor som alla i en grupp svarat ja pÄ, och Àven hur mÄnga frÄgor minst en person i en grupp svarat ja pÄ.
Det finns 26 möjliga frÄgor, representerade som en bokstav frÄn a till z.
Det som dÄ ligger nÀra till hands Àr att spara den hÀr informationen, om vilka frÄgor man svarat ja eller nej pÄ genom bitar i ett 32-bitars heltal! Som i kodsnutten nedan:
c = getchar();
if (c >= 'a' && c <= 'z') {
answer_mask_current |= 1 << (c - 'a');
(c - 'a') rÀknar alltsÄ ut en siffra frÄn 0 till 25 genom att ta ASCII-vÀrdet för bokstaven med svaret som passageraren svarat ja pÄ, och sedan dra bort ASCII-koden för A. T.ex. 'a'-'a' blir dÄ 0, och 'b'-'a' blir dÄ 1 etc.
1 << (c - 'a') tar vÀrdet 1 och "skiftar vÀnsterut med (c - 'a') steg. D.v.s. för 'e' sÄ blir 'e'-'a' till 4, och 1 << 4 blir 16 (eller 0b00010000, 1:an har hoppat 4 steg till vÀnster.)[/cmd]
answer_mask_current |= 1 << (c - 'a'); Gör en "bitwise or", vilket betyder att i det nya vÀrdet för answer_mask_current sÄ blev varje bit i detta vÀrde 1 om antingen biten redan var 1, ELLER om biten vi rÀknade fram nedan (som motsvarar svaret vi registerat) Àr 1. D.v.s. pÄ detta sÀtt kan vi slÄ pÄ den bit som motsvarar ja-svaret.
I slutet av raden sÄ har vi dÄ att answer_mask_current innehÄller ett bitfÀlt, dÀr varje 1-satt bit i vÀrdet representerar en frÄga som nÄgon svarat ja pÄ.
NÀr vi sedan nÄr slutet av raden kommer vi hit:
answer_mask_any |= answer_mask_current;
answer_mask_all &= answer_mask_current;
answer_mask_current = 0;
Första raden, samma sak, i answer_mask_any slĂ„r vi PĂ
alla bitar dÀr den nuvarande passageraren svarat ja. Resultatet blir att i answer_mask_any sÄ blir en frÄgas bit 1 om minst en person i gruppen svarat ja pÄ frÄgan.
Andra raden blir lite klurigare. HÀr börjar vÀrdet som ~0 (eller alla bitar som 1:or), och istÀllet sÄ stÀnger denna rad AV bitar i answer_mask_all dÀr passageraren svarat nej! Resultatet blir att bitarna answer_mask_all bara Àr satta om ingen svarade nej pÄ frÄgorna (d.v.s. alla svarade ja).
Tredje raden nollstÀller answer_mask_current sÄ att vi kan kolla pÄ nÀsta rad.
Om vi kommer till slutet pÄ en rad (eller för all del till slut pÄ filen), och answer_mask_current Àr noll, dÄ vet vi att vi har fÄtt en tom rad (hade det funnits nÄgra svar sÄ hade minst 1 bit vart satt...). D.v.s. slut pÄ gruppen, och dags att rÀkna hur mÄnga frÄgor alla svarat ja pÄ, samt alla frÄgor minst en svarat ja pÄ.
Det Àr hÀr instruktionen POPCNT kommer in! Vi vill rÀkna hur mÄnga bitar i answer_mask_anyoch answer_mask_all som Àr satta till 1, och det Àr exakt vad popcount gör!
else if (c == '\n' || c == EOF) {
if (answer_mask_current == 0) {
part1 += __builtin_popcount(answer_mask_any);
answer_mask_any = 0;
part2 += __builtin_popcount(answer_mask_all);
answer_mask_all = ~0;
} else { /* ... */ }
}
Efter att vi rÀknat bitarna nollstÀller vi answer_mask_anyoch answer_mask_all till dess utgÄngsvÀrde, sÄ att vi kan börja frÄn scratch i nÀsta grupp.
