Vektorisierte CLZ und CTZ: Bits zählen mit Fließkomma-Tricks

Vectorized CLZ and CTZ

clz und ctz berechnen führende bzw. nachfolgende Nullbits. Der Autor zeigt, wie sich beide mit Fließkomma-Arithmetik vektorisieren lassen: Bei clz wird x in die Mantisse einer Zweierpotenz geschrieben und der Exponent extrahiert; bei ctz wird das niedrigste gesetzte Bit isoliert und über eine vorbereitete Mantisse ausgelesen. Auf Haswell laufen die Vektorversionen in 0,45 bzw. 0,49 ns pro Iteration, verglichen mit 1 ns skalar. Zusätzlich wird eine de-Bruijn-Sequenz-Variante vorgestellt.