Population count für große Bit-Felder

Die Funktion, die die Anzahl der gesetzten Bits in einem binären Wort ermittelt wird population count oder side way addition genannt. Imfolgenden werden wir sie kurz popc nennen.

Dieser Funktion kommt in verschieden Zusammenhängen vor. Manche Computer haben sogar einen speziellen Machinenbefehl dafür, z.B SADD (bei der Mark I), POPCNT (eine SSE4.2 Instruktion) or VPCNT (bei der NEC SX-4).

Da viele aktuelle Architekturen (wie die Intel i386) keine Maschinebefehl für den population count haben, sind Algorithmen die den population count auf einfache logische und arithmetische Operationen zurückführen interessant.

Zusammen mit Y. Edel habe ich einen Algorithmus entwickelt, der die gesetzten Bits in den Spalten einer Matrix zählt. Dieses Problem taucht bei gewissen Anwendungen in der Kryptographie auf und ist auch auf Maschinen mit eingebauten population count nicht trivial. Hier ist die zugehörige Veröffentlichung (in Englisch).

Wir haben unsere Algorithmen in C implementiert. Dabei benutzen wir ein von mir neu entwickeltes literate programming System zum Kommentieren des Codes.

Der Quellcode von unserem Programm ist hier. Man kann sich auch direkt den C Quellcode oder die PDF Dokumentation herunter laden.