Gerne. In diesem konkreten Fall brauche ich den Zahlenbereich (0, 64) - war die Notation so? Ich meine: von einschließlich 0 bis einschließlich 64.
Dann gibt es da die Funktion "Finde das höchste gesetzte Bit". Die sieht auf GCC so aus:
Code: Alles auswählen
/// Ermittelt den Index des höchsten gesetzten Bit (von 0 an zählend) aus der gegebenen Zahl, oder gibt SIZE_MAX zurück bei kompletter Leere
inline size_t FindeHoechstesBit(uint64_t z)
{
static_assert(sizeof(z) == 8, "Hardcoded auf 64bit");
// absichtlicher Overflow: falls z == 0, ergibt clz(z) 64, demzufolge ergibt die Subtraktion -1
return size_t( 63) - size_t( __builtin_clzll(z));
}
"clz" steht wohl für "Count Leading Zeros". Die Funktion soll für den kompletten
uint64_t-Range funktionieren, natürlich nur
unsigned. Das funktioniert so ohne Conditional und alles,
solange ich mich darauf verlassen kann, dass 63 - 64 auch SIZE_MAX ergibt.. Aber wenn ich euch richtig verstehe, ist Integer Overflow für
unsigned-Typen wohldefiniert, also müsste das klappen.
Dann gibt es da die Funktion "Finde das niedrigste gesetzte Bit". GCC-Version:
Code: Alles auswählen
/// Ermittelt den Index des niedrigsten gesetzten Bit (von 0 an zählend) aus der gegebenen Zahl, oder gibt SIZE_MAX zurück
inline size_t FindeNiedrigstesBit(uint64_t z)
{
return size_t(__builtin_ffsll(z)) - 1;
}
"ffs" steht wohl für "Find First Set". Ebenso für kompletten
uint64_t-Bereich, ebenso nur
unsigned. Und auch die Funktion funktioniert so nur, wenn 0 minus 1 auch SIZE_MAX ergibt.
Und zum Schluss noch die "Zähle gesetzte Bits"-Funktion:
Code: Alles auswählen
/// Ermittelt die Anzahl gesetzter Bits in der gegebenen Zahl
inline size_t GetAnzahlEinsen(uint64_t z)
{
return size_t(__builtin_popcountll(z));
}
Da gibt's nix zu Grübeln dran.
Die VC-Versionen davon sind je nach Define entweder per Intrinsic oder über die alten Bit-Tricks von dieser einen Webseite implementiert. Mit "Intrinsics" meine ich hier allerdings _BitScanReverse() und Konsorten - es gäbe wohl noch "richtige" Intrinsics für diesen Job. Nur das Einsen-Durchzählen ist schon ein __popcount() und hatte mir damals auch prompt einen Strauß Crashes mit der Vor-Steam-Version von Splatter gebracht, weil ich zu arglos SSE4 vorausgesetzt habe. Seitdem gibt es die Bithack-Version für ältere Prozessoren.
