Schwere Aufgabe (2er-Komplimentär)



  • Ich hab hier eine Aufgabe, die ich ziemlich krass finde.

    Aufgabe: In einem Zahlensystem, das auf dem 2-Komplimentär beruht, löscht der Ausdruck x &= (x-1) das rechteste Bit mit Wert 1 in x. Erklären sie warum. Benutzen sie diesen Trick, um eine schnellere Version von bitcount zu realisieren.

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


  • Ich steuer mal fix was zur 1. Aufgabe bei (Erklären warum): x&=(x-1) ist ja nichts anderes als x=x&(x-1). D.h. x wird mit sich selber UND-verknüpft, nur dass beim zweiten Operanden (also x-1) das hinterste Bit 0 gesetzt wird, wenn es 1 war. Wenn es hingegen 0 war, wird es 1 gesetzt.
    Z.B.: x=2: (2-1)10=110, dual: 10-1=01.
    x=3: (3-1)10=210, dual: 11-1=10

    Durch den obigen Ausdruck wird das hinterste Bit also immer umgedreht. x&(x-1) ergibt dann auf der hintersten Bitstelle immer eine 0, weil 0&1 sowie 1&0 0 ergibt.

    Die Funktion schau ich mir gleich mal an...



  • Hab mal fix was gemacht, musst du aber selbst testen, ob das funzt:

    int bitcount(unsigned x){
    	int b=0;
    	while(x){
    		x&=(x-1);
    		b++;
    	}
    	return b;
    }
    

    Begründung: durch x&=(x-1) wird immer ein 1-Bit aus x entnommen. Wenn keine 1-Bits mehr in x sind, bricht die Schleife ab und du hast deine 1-Bit-Anzahl.
    Wie gesagt, hab es nicht ausprobiert. Schreib mal, ob es so funktioniert.



  • Ich bin noch kurz an der anderen Aufgabe dran... aber gleich lese ich kurz nochmal was, wegen den bedingten Ausdrücken und dann diskutieren wir nochmal da drüber okay ? 💡



  • "...wegen den bedingten Audrücken...".
    Öhm, was meintest du damit? if-else?!
    Aber egal: ok!



  • int bitcount(unsigned x){ 
        int b=0; 
        while(x){ 
            x&=(x-1); 
            b++; 
        } 
        return b; 
    }
    

    Um wieviel schneller ist denn die neue Funktion gegenüber der alten oder ist das nicht so leicht bestimmbar ?

    Ich hab erstmal das Grundprogramm geschrieben:

    #include <stdio.h> 
    
    #define SIZE 10 
    
    int lower (char c); 
    
    int main(int argc, char* argv[]) 
    { 
      int x; 
      char eingabe1[SIZE], Ergebnis[SIZE]; 
      /* "x" ist die Hochzählvariable für die eingabe1 und Ergebnis. Hierbei
      werden alle Postionen des Array leer geschrieben, damit kein Wert
      noch vorhanden ist und die Berechnung verfälscht */
      for(x = 0; x <= (SIZE-1); x++)
      {
        eingabe1[x]=' ';
        Ergebnis[x]=' ';
      }
      printf("Eingabe 1:\n");
      /* fgets sorgt dafür, dass nicht mehr Zeichen eingelesen werden, als
      die maximale Größe vorschreibt */
      fgets(eingabe1,SIZE,stdin);
      /* "x" ist wieder eine Hochzählvariable, die die einzelnen Zeichen
      durchgeht und komplett die gesamte Eingabe durcharbeitet. Danach
      wird das Ergebnis in Array gespeichert, der dann später bei der
      Ausgabe wieder angesprochen wird */
      for(x = 0; x <= (SIZE-1); x++)
      {
        Ergebnis[x] = bitcount(eingabe1[x]);   
      } 
      printf("Das Ergebnis ist:\n"); 
      for(x = 0; x <= (SIZE-1); x++) 
      { 
        printf("%d", Ergebnis[x]); 
      } 
      return 0; 
    } 
    
    int bitcount(unsigned x)
    {
      int b;
      for (b = 0; x != 0; x >>= 1)
        if (x & 01)
          b++;
      return b;
    }
    


  • Könntest du erstmal schreiben, ob die auch funktioniert, die Funktion?
    Geschwindigkeit lässt sich schwerer ermitteln, aber ich könnte es versuchen, wenn die Funktion so richtig ist...



  • Ist eigentlich sogar sehr genau möglich.
    Ich könnte es auch testen und dann könnten wir vergleichen!
    Dafür sollt ich auch wissen ob das so läuft wies da steht!



  • int bitcount(unsigned x){ 
        int b=0; 
        while(x){ 
            x&=(x-1); 
            b++; 
        } 
        return b; 
    }
    

    Diese besagte Funktion funktioniert, wenn man sie in das obige Programm einbaut und gegen die andere tauscht.

    Die Ausgabe kann aber noch net ganz stimmen. Es sollen ja nur 0er und 1er ausgegeben werden, von einem Wert, den man eingegeben hat.
    Wie muss printf dafür geschrieben werden, damit das ohne Probleme funktioniert.



  • Die sind glaubich gleich schnell!!!

    toll:
    0010
    0110
    ------- &
    0010 = 0x2 = 2 = 1 + 1



  • Die Funktion, die da steht, liefert mir doch 0en und 1en oder ?

    Also wenn ich in der Eingabe einen Buchstaben eingebe, wird mir durch Funktion, die Anzahl der 0en und 1en angezeigt oder ? 😕



  • Hallo Teilnehmer?!

    Die Funktion liefert EINEN int-Wert zurück, wie soll sie dann 0en und 1en zurückliefern?!

    Guck dir das doch mal an: die Funktion sollte die Anzahl von Einsen zurückliefern, die Anzahl der Nullen kannst du dann leicht berechnen, indem du den zurück gelieferten Wert von der Anzahl der Bits einer int-Zahl (na wieviel sind das wohl?) subtrahierst!

    Ich würde aber schon sagen, dass das schneller ist: weil du ja nicht alle Bitstellen betrachten musst, sondern die while-Schleife nur sooft läuft, wie du 1-Bits in der Zahl hast. Im günstigsten Fall läuft sie also gar nicht (wenn die Zahl 0 ist), im ungünstigsten Fall läuft sie sooft wie lang die Dualzahl ist (wenn sie aus lauter 1en besteht).
    Bei der ersten Version wird hingegen JEDE Bitstelle betrachtet, die Schleife läuft also immer den ungünstigsten Fall durch.

    Im Mittel sind also um die Hälfte weniger Schleifenaufrufe erforderlich!



  • Gibts denn nicht ein Programm das kontrolliert, wie lange die Laufzeit eines anderen Programmes so ist ? 🕶



  • Ich hab vor ein paar Jahren ne richtig gute Stoppuhr schenken lassen, misst im Bereich von Nanosek.. Ist aber nicht ganz billig. Entweder schaust du mal bei ebay nach oder meld dich mal per mail bei mir da ich langsam alt werde. Und man weiß ja das im zunehmenden Alter die Reflexe langsam aber sich einfrieren.

    Cu



  • LOL guter Kommentar 🤡



  • grenouille_unreg schrieb:

    Ich hab vor ein paar Jahren ne richtig gute Stoppuhr schenken lassen, misst im Bereich von Nanosek.. Ist aber nicht ganz billig. Entweder schaust du mal bei ebay nach oder meld dich mal per mail bei mir da ich langsam alt werde. Und man weiß ja das im zunehmenden Alter die Reflexe langsam aber sich einfrieren.

    Cu

    Richtig lustig der Herr 😉

    Boah ich merke eben, dass des totale Kacke ist mit den Arrays irgendwie bei dem Programm.
    Ich bekomme da einen Wert weit über die Million raus bei der Ausgabe !



  • Ich wollte mich nicht auf deine Kosten amüsieren. Ich wollte zum Ausdruck bringen das du erstmal den Algo von bitcount richtig verstehst. Den aus dein Postings geht hervor das dein Wissen über Bit-Operatoren zieml. begrenzt ist.



  • Ich bin ein Dumschwätzer!!!



  • grenouille_unreg schrieb:

    Ich bin ein Dumschwätzer!!!

    Nene ich hab noch etwas nachzulesen, wegen den Bit-Operatoren, aber ich arbeite mich heran und versuche noch mehr Wissen dazu zu bekommen.

    Hast du denn eine Idee, wie man das Programm komplett anders schreiben kann ?



  • Weißt du eigentlich dass ich viel zu gutmütig bin?!
    Also, folgendes Programm liefert auf meinem Rechner folgende Ausgabe:

    Wieviele Durchlaeufe?: 10000000
    
    bitcount():       2.340 Sekunden
    bitcount_impr():  0.710 Sekunden
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <limits.h>
    
    int bitcount(unsigned x){ 
    	int b; 
    	for (b = 0; x != 0; x >>= 1) 
    		if (x & 01) 
    			b++; 
    	return b; 
    }
    
    int bitcount_impr(unsigned x){ 
        int b=0; 
        while(x){ 
            x&=(x-1); 
            b++; 
        } 
        return b; 
    }
    
    int main(void){
    	int i, n;
    	unsigned int *x;
    	clock_t start, ende;
    	srand(time(0));
    
    	printf("Wieviele Durchlaeufe?: ");
    	scanf("%d",&n);
    
    	x=(unsigned int*)malloc(n*sizeof(unsigned int));
    
    	for(i=0; i<n; i++)
    		x[i]=rand()%INT_MAX;
    
    	start=clock();
    	for(i=0; i<n; i++)
    		bitcount(x[i]);
    	ende=clock();
    	printf("\nbitcount():      %6.3f Sekunden\n",(ende-start)/(float)CLOCKS_PER_SEC);
    
    	start=clock();
    	for(i=0; i<n; i++)
    		bitcount_impr(x[i]);
    	ende=clock();
    	printf("bitcount_impr(): %6.3f Sekunden\n\n",(ende-start)/(float)CLOCKS_PER_SEC);
    
    	free(x);
    	return 0;
    }
    

    Kannst die Durchläufe natürlich nach Belieben variieren. 10 Millionen erschienen mir aber erstmal angemessen. Viel Spaß damit...


Log in to reply