binäre Quersumme einer Zahl

[frager (Gast)]

wie genau funktioniert das Alg? ist es irgendwo beschrieben? Danke!

int bitcount8 (byte w)
{
    w = (byte)(0x55 & w) + (byte)(0x55 & (byte)(w >> 1));
    w = (byte)(0x33 & w) + (byte)(0x33 & (byte)(w >> 2));
    w = (byte)(0x0F & w) + (byte)(0x0F & (byte)(w >> 4));
    return w;
}

[Yalu X. (yalu) (Moderator)]

b0 bis b7 seien die Bits des ursprünglichen Bytes w. Damit werden
folgende Rechenschritte ausgeführt:

Erster Schritt:
s01 = b0 + b1
s23 = b2 + b3
s45 = b4 + b5
s67 = b6 + b7

Zweiter Schritt:
s0123 = s01 + s23
s4567 = s45 + s67

Dritter Schritt
s01234567 = s0123 + s4567

Dies ist die Summe aller 8 Bits.

Dabei wird in jedem Schritt dafür gesorgt, dass sich die Bits der
jeweiligen Ergebnisse innerhalb des Bytes w nicht überlappen.

Am besten gehst du das Ganze anhand eines Beispiels durch, dann weißt
du, wie der Hase läuft.

[Johann L. (gjlayde)]

Falls man gcc verwendet geht auch

return __builtin_popcount (w);