Wie viele einsen kommen vor?

[sheel]

Das << hab ich oben noch dazueditiert.

Zum bis 7 zählen: Da hast du einen Fehler
es soll heißen "<8", hab ich oben auch ausgebessert
Warum? Jetzt zählt er 01234567, das sind die 8 Bit in einem unsigned char.

&: Nennt man das binäre Und.

Wenn man zwei Zahlen damit verrechnet (und die Zahlen binär betrachtet), wäre das ca. sowas:

01010101
&00111100
=00010100

Es bleibt also nur 1 übrig, wo bei beiden Zahlen 1 steht.
Das Ganze in einem if ergibt dann Wahr, wenn min. eine 1 übriggeblieben ist

Wie ich das hier brauche?

Beispiel mit 23:
23 ist 00010111

Erster Schleifendurchgang: i ist 0, ret ist 0
i<<i ist i<<0, also Null Mal verschieben, ist 00000001
00010111 & 00000001 ist 00000001, ist Wahr, also ret eins raufzählen ist 1.

Zweiter Schleifendurchgang: i ist 1, ret ist 1
i<<i ist i<<1, also den Einser einmal verschieben, ist 00000010
00010111 & 00000010 ist 00000010, ist Wahr, also ret eins raufzählen ist 2.

Usw.

 

[marvellous]

danke hammer hilfe

 

[Matthias Reitinger]

Hallo,

man kann das Problem natürlich auch mit der schon erwähnten Modulo-Operation lösen, z.B. so:

unsigned char weight(unsigned char x) {
  unsigned char ret = 0;
  while (x != 0) {
    ret += x % 2;
    x /= 2;
  }
  return ret;
}

Grüße,
Matthias

 

[deepthroat]

Hi.

Mir ist das Problem unter dem Namen "Population Count" bekannt.

Man kann dies auch mit verschiedenen Algorithmen ganz ohne Schleife und Bedingung berechnen.

Sehr populär ist der HAKMEM 169 Algorithmus. Siehe z.B. http://wiki.cs.pdx.edu/forge/popcount.html

Gruß