Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
12.05.2004, 17:02 Uhr
Beginner

Hallo, habe ein Problem. Wenn ich eine Zahl definiere und rausbekommen will, wieviele Einsen in der Binärform vorkommen gibt es die Funktion:

C++:

int bitcount(unsigned x)
{
    int b;
    for(b=0;x!=0;x>>1)
        if(x&01)
           b++;
return b;
}

ich habe es jetzt mal ohne Funktionsübergabe probiert und es kommt für die Zahl 255 wirklich 8 (Anzahl der Einsen) heraus.

C++:

#include<stdio.h>

int main(void)
{
    int b,x=255;
    for(b=0;x!=0;x>>=1)
        if(x&1)
            b++;
        printf("%d",b);
        return 0;
}

Aber irgendwie kann ich die for Schleife nicht ganz nachvollziehen. Also b startet bei b=0 und wenn die if Bedingung erfüllt ist, wird nach jedem durchlauf b um eins erhöht. Das mit dem x!=0 verstehe ich nicht ganz.Wird wohl sowas wie solange x!=0 bedeuten.Aber gehe ich dann noch von den 255 aus, oder dem Binärwert. x>>=1 bedeutet, daß nach jedem Durchlauf links eine Null eingeschoben wird und die rechte Stelle herausfliegt oder? Wäre nett, wenn mir das mal jemand erkären könnte.

Grüße

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
12.05.2004, 17:38 Uhr
Pablo
Supertux
(Operator)

x>>1 bedeutet bits nach rechst shiften. Ein Register (sagen wir mal ein 8-bit Register) hat 8 Bits. Das kannst du dir als ein Stapel vorstellen, wobei unten (oder links) die niederwertigsten Bits und oben (oder echts) die höherwertigsten Bits sind.

Eine Shift Operation verschiebt alle Bits, entweder nach Links oder nach Rechts.
Angenommen: x=10001101 wird x>>1 ist 01000110. Sieht du den Unterschied? Der ganze Block wurde um eine Stelle nach rechts verschoben, und die neuen Stellen werden mit 0 gefüllt. Die letzte 1 von der 1 geht in diesem Fall verloren.

D.h., wenn du (im meinem Beispiel) 8 mal nach rechts shiftest, dann bekommst die zahl 0, denn dann hätte dein Register 00000000, denn jedesmal, dass es nach rechts verschoben wird, erschient ganz rechts eine 0, d.h. in höchstens 8 Schritten haben wir eine 0.

x>>=1 ist äquivalent zu x=x>>1, d.h. weise in x den Wert von "x nach rechts geschifftet" zu. Es ist logisch, dass x irgendwann 0 sein wird, wenn das passiert, kommen wir von der For Schleige raus, das x!=0 FALSE liefert.

x&1 bedeutet, vergleiche alle Bits von x mit der 1 mit dem Operator AND. Du weißt, dass

Code:

x | y | x&y
---------------
0 | 0 | 0
---------------
0 | 1 | 0
---------------
1 | 0 | 0
---------------
1 | 1 | 1

Das heißt, dann x&1 ist äquivalnet zu x&00000001. Angenommen x=11001101. Dann ist x&1

Code:

1 1 0 0 1 1 0 1
0 0 0 0 0 0 0 1
------------------------ &
0 0 0 0 0 0 0 1 = 1 im Dezimalsystem.

if (x&1) bedeutet, wenn x AND 1 eine 1 liefert, dann gibt es an der 0. Stelle eine 1, also b++ (b ist der Zähler). Dieser Trick heißt Maskierung, damit kannst du enzelne Bits eine Binäerzahl herausfinden.

Bsp:
x=00000101 = 5
Wenn ich wissen will, ob das 3. Bit von den 8 Bits gesetzt, mache ich folgendes
if (x&4==4) ==> durch die Maskierung bekomme ich 00000100=4
Oder if (x&8==0) ==> das 4. Bit ist nicht gesetzt, also 0 (in unserem Bespiel würde x&8==0 TREU liefern)
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Dieser Post wurde am 12.05.2004 um 17:43 Uhr von Pablo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
12.05.2004, 20:51 Uhr
Beginner

Danke das hat mir schonmal sehr weiter geholfen.

Nun habe ich noch eine Aufgabe und eine von mir erstellte Antwort dazu. Vielleicht kannst du mir sagen, ob ich mir meiner Antwort richtig liege.

Aufgabenenstellung: In einem Zahlensystem, das auf dem 2-Komplement beruht, löscht der Ausdruck x&=(x-1) das rechteste Bit mit Wert 1 in x. Erklären Sie warum?

Antwort: Um ein Zweier - Kompement bilden zu können, muß ich zuerst das Einer Komplement bilden ( Alle Bits des Bitmusters negieren) und dann das einer Komplement mit +1 addieren.
Also ist mein x irgenein Bitmuster mit einer Eins am rechten Ende.

Mein x&=(x-1) entspricht x=x&(x-1)
Nun betrachte ich die letzte Stelle von x die 1 ist und die letzte Stelle von (x-1) bei der das letzte bit dann 0 ist. Insgesamt ergibt das also:

C++:

.......1
          .......0 &
          ---------
          .......0

Also so habe ich es jetzt verstanden. Kann man so eine Begründung zählen lassen?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
12.05.2004, 21:40 Uhr
Pablo
Supertux
(Operator)

Was meinst du mit löscht? Dass das 0. Bit auf 0 gesetzt wird?

Das ist ganz einfach zu erklären. Seien x,y 2 Zahlen in 2-Kom.
[x]-[y]=[x]+[y']+1, wobei y' die negation von y ist.

Du hast folgednes: [x]-1=[x]+<1.....10>+1.
Wenn das 0. Bit von x eine 0 ist. 1' an der Stelle 0 hat eine 0, 0+1=1.
Dann hast du folgende Summe

Code:

x=? ? ? ··· ? 0
1'=1 1 1 ···1 1
---------------- +
=? ? ? ··· ? 1 = x-1

Aus x=x&(x-1) ==> 0&1=0 (beachte ganz rechts, die 0. Stelle).

Wenn das 0. Bit von x eine 1 ist ==> 1' an der Stelle 0 eine 0 haben wird und 0+1=1.
Dann hast du folgende Summe

Code:

x=? ? ? ··· ? 1
1'=1 1 1 ···1 1
---------------- +
=? ? ? ··· ? 0 = x-1

Die Maskierung ist 1&0=0 (beachte ganz rechts, die 0. Stelle).

Wenn du 1 subtrahierst, musst du auf jeden Fall das 0. Bit komplementieren, denn das 0. Bit 2^0 entspricht und damit kodiert man die ungerade Zahlen. Also haben x und x-1 immer an der 0. Stelle unterschiedliche Bits, wenn du sie mit AND verknüpfst, ist logisch, dass 0 dabei rauskommt.
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Dieser Post wurde am 12.05.2004 um 21:41 Uhr von Pablo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
12.05.2004, 22:25 Uhr
(un)wissender
Niveauwart

Na, es geht nicht um das nullte Bit, sonder um das rechteste Bit mit einer eins, dass kann das 0te Bit sein, aber auch das 1, usw.
Z.B.:
110 &= 110 + 111(-1) = 100 <-hier wird das zweite (bzw. das erste

)gelöscht.
--
Wer früher stirbt ist länger tot.

Dieser Post wurde am 12.05.2004 um 22:26 Uhr von (un)wissender editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
12.05.2004, 23:52 Uhr
Pablo
Supertux
(Operator)

Im Prinzip ist die Erklärung ähnlich.
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Dieser Post wurde am 12.05.2004 um 23:52 Uhr von Pablo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
13.05.2004, 08:37 Uhr
(un)wissender
Niveauwart

Ich dachte ihr Mathematiker nehmt es genau, also mit so einer Aussage ernte ich nur ein müdes Lächeln von Profs

.
Aber ich versuche es auch immer wieder

.
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
13.05.2004, 10:54 Uhr
Pablo
Supertux
(Operator)

Da habe ich als Informatiker bewiesen. Naja, also hier die Erklärung.

Angenommen ist das k. Bit (von einem n Bit Register) eine 1. D.h. Das k. Bit von 1'+1 wird ebenfalls eine 1 sein. 1+1 = 0 mit Übertrag 1. Also ist die Addition an der k. Stelle eine 0 mit Übetrag 1. Die k. Stelle bekommt keinen Übertrag, weil davor nur 0 waren.
x[k] = 1 ==> (x-1)[k]=0 ==> (x&(x-1))[k]=0
--
A! Elbereth Gilthoniel!
silivren penna míriel
o menel aglar elenath,
Gilthoniel, A! Elbereth!

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
13.05.2004, 14:53 Uhr
(un)wissender
Niveauwart

Pablo, Beweis ist Beweis, ob nun als Informatiker, Mathematiker oder als BWLer (OK, denen genügt ein volles Konto als Beweis).
--
Wer früher stirbt ist länger tot.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
13.05.2004, 16:24 Uhr
virtual
Sexiest Bit alive
(Operator)

Übrigens:

C++:

int bitcount (unsigned int n)
{
   n = (n & 0x55555555) + ((n >> 1) & 0x55555555) ;
   n = (n & 0x33333333) + ((n >> 2) & 0x33333333) ;
   n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f) ;
   return n % 255 ;
}

Ist schnell und praktisch und so.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: