# Wie viele einsen kommen vor?



## marvellous (19. Dezember 2010)

ich bin im1. Semester und bereite mich auf die Prüfungen vor.
Ich hänge grad an ein er Aufgabe: http://nk.stzre.de/upload/downloads/2009_i1_pr_ss09.pdf 
Die Nr. 3.
_________________________________________________________________
Als Gewicht einer Variablen bezeichnet man die Anzahl der binären Einsen, die die
Zahl besitzt. Zum Beispiel besitzt die Variable x mit unsigned char x=23; das
Gewicht 4 (23 =00010111).
Schreiben Sie die Funktion weight(), die als Übergabeparameter die zu
untersuchende Variable x vom Typ unsigned char erhält und das Gewicht als
Rückgabewert zurückliefert.
_________________________________________________________________


Versteh ich die Aufgabe überhaupt richtig? Soll ich mit dem gegebenen Beispiel ein Programm erstellen?
Meine Überlegungen: Eine Schleife, welche die einzelnen Zahlen vergleicht und bei 0 zur nächsten Zahl überspringt, aber ich weiß leider nicht wie ich das umsetzen kann.


----------



## sheel (19. Dezember 2010)

Willkommen bei tutorials.de 

Kennst du dich mit den Operatoren << und & aus bzw. dürft ihr die verwenden?


```
char weight(unsigned char x)
{
    char ret=0,i;
    for(i=0;i<8;i++)
    {
        if(x&(1<<i))
            ret++;
    }
    return ret;
}
```

Gruß


----------



## marvellous (19. Dezember 2010)

was das wars schon?!  Ja ich denke wir dürfen die verwenden.
<< bedeutet doch verschieben oder sowas oder?


----------



## Crash Kid (19. Dezember 2010)

Hey,

also so wie ich es verstehe, musst du die übergebene Zahl x (z.B. 23) erst in die binäre Form umrechnen und dann eben die 1en zählen. Sieht auf den ersten Blick nicht all zu schwer aus. Einzige was schwiriger ist, die binäre Form auszurechnen. Aber da musst dir halt ne Funktion überlegen 

grüße


----------



## sheel (19. Dezember 2010)

@Crash Kid: Warum extra umrechnen? Schau dir doch den Code mal an, das kann man sich auch sparen.

@marvellous: Ich habs zwar nicht ausprobiert, aber ja, das wars 
Ich mach noch einen Test...

edit: Code ist Korrekt.

edit2: << kann man mit "nach links verschieben" gleichsetzen, ja.

zB:
00000001 einmal verschieben ergibt
00000010, nocheinmal ergibt
00000100 usw.

Wenn man die Zahlen ins Dezimale umrechnet, sieht man, dass es auch gleichzeitig "mal 2" bedeutet
Die Zahlen von oben sind 1, 2 und 4
00001000 wäre dann 8.

Noch ein Sinn dahinter:
1<<xyz kann man deshalb mit "1 mal (2 hoch xyz)" gleichsetzen.
Das "1 mal" fällt sowieso weg, übrig bleibt:
1<<xyz bedeutet 2 hoch xyz.

Gruß


----------



## Crash Kid (19. Dezember 2010)

Wie ich meine Antwort geschrieben habe, gabs den Code noch nicht . Schau mal auf die Uhrzeit, wir haben zeitgleich geantwortet...


----------



## marvellous (19. Dezember 2010)

http://upload.wikimedia.org/math/c/1/c/c1c6f725e216b29741f35c83d2eb7f25.png
das hab ich grad auf wikipedia gefunden=D
also 23%2 dann bekomm ich ja 11 rest 1 raus
dann 11%2 = 5 rest 1
5 % 2 = 2 rest 1
2 %2 = 1 rest 0
1 % 2 = 0 rest 1

10111  so in der art oder?


----------



## Crash Kid (19. Dezember 2010)

Genau. So kannst du die Ganzzahl in ihre binäre Form umrechnen. Aber laut sheel, brauchst du das mit dem obigen Code nicht. Ich hab ihn nicht ausprobiert, aber er wollte es ja noch testen.

gruß


----------



## marvellous (19. Dezember 2010)

ja er hats ja schon editiert  funktioniert..hm könnt ihr mit das mit dem & und << kurz erklären?
oder warum wird nur bis 7 gezählt ?


----------



## marvellous (19. Dezember 2010)

ahja hast jetzt auf 8 geändert 
ok hab den code kapiert das ist auch die aufgabenstellung odeR?  oder doch mit umwandeln********  ansonsten dankeschön


----------



## sheel (19. Dezember 2010)

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 (19. Dezember 2010)

danke hammer hilfe


----------



## Matthias Reitinger (19. Dezember 2010)

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 (20. Dezember 2010)

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ß


----------

