Schwere Aufgabe (2er-Komplimentär)



  • 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...



  • grenouille_unreg schrieb:

    Ich bin ein Dumschwätzer!!!

    Kommt davon wenn man als unreg hier beiträge verfasst. Sorry war ich jedenfalls net.

    Mir wäre es lieber wenn du Depp nächstes mal in der 3.Person schreiben würdest. Und schau mal bitte im Du"hh"den wie man "Dumschwätzer" schreibt.



  • Achso, die Richtigkeit der verbesserten Funktion habe ich auch noch an ein paar Beispielen gezeigt - also ist alles in Butter...



  • Weißt du eigentlich dass ich viel zu gutmütig bin?!

    Ja und das find ich auch gut. Solche Menschen gibt es nicht so oft auf dieser Welt *g*. Das Programm wird mir auf jeden Fall weiterhelfen !

    THX 😉



  • cHillb3rT schrieb:

    Weißt du eigentlich dass ich viel zu gutmütig bin?!

    Ja und das find ich auch gut.

    Ist es aber nicht unbedingt - schließlich wird es dir woanders auch nicht leicht gemacht und vorgekaut. Also versuche lieber mal vorher zu überlegen und zu lernen und dann zu posten, das ist ein viel besserer Weg und man macht sich nicht soviele Feinde!

    Noch ein Beispiel für 100 Millionen:

    Wieviele Durchlaeufe?: 100000000
    
    bitcount():      23.390 Sekunden
    bitcount_impr():  7.040 Sekunden
    

    Man sieht schön, dass die verbesserte Funktion nur ca. 30% der Zeit von bitcount() benötigt, also mehr als 3-mal so schnell ist...


Anmelden zum Antworten