Größte Zweierpotenz



  • Hallo!
    Könnte mir jemand bei der Aufgabe helfen? Ich habe versucht , allein zu lösen aber das Ergebnis ist nicht korrekt.
    Aufgabe : Schreiben Sie ein Programm, das eine natürliche Zahl einliest und die größte Zweierpotenz ausgibt, die die eingelesene Zahl teilt.

    #include <iostream>
    using namespace std;
    
    int main() {
    
    	int n, counter{0};
    	cin >> n;
    
    	do
    	{
    		n / 2;
    		counter++;
    	} 
    	while (n % 2 != 0);
    	if (n % 2 == 0) 
    	{
    		cout << "Die groesste Zweierpotenz ist " << pow(2, counter) << ".\n";
    	}
    	else
    	{
    		cout << "Die groesste Zweierpotenz ist 1.\n";
    	}
    
    	return 0;
    


  • @Xerodus sagte in Größte Zweierpotenz:

    die eingelesene Zahl teilt.

    Teilt ... ohne Rest?



  • Sowas:

    int n = <zahl einlesen>;
    int groesstePotenz = 1;
    for (int p = 1; p <= n; p *= 2) { 
        if (n % p == 0) groesstePotenz = p; 
    }
    <groesstePotenz ausgeben>;
    


  • @wob ist das nicht sehr ineffizient? Ich würde bei der zu n nächstkleineren Zweierpotenz anfangen.



  • Laufzeit ist logarithmisch. Also würde ich nicht von ineffizient sprechen (darum geht es hier sicher auch nicht).

    Ich hatte das auch erst überlegt, aber dann ist die Frage: wie ermittle ich die "nächstkleinere" (die auch gleich sein darf) Zweiterpotenz? Man kann log2n\log_2 n bemühen, aber dann muss ich 2x den log berechnen, teilen und ggf. runden, das ist auch nicht effizient. Alternativ irgendwie mit Bits rumspielen, um das hi-Bit von n zu bekommen. Aber das ist auch Aufwand. Und sowas wie __builtin_clzll wollte ich hier nicht verwenden.


  • Mod

    Ist die Frage nicht äquivalent dazu, die "Nullen" rechts in der Binärdarstellung zu zählen?



  • @SeppJ yay 🙂



  • Dann Folgeaufgabe: größte Dreierpotenz!




  • Mod

    Wenn wir uns da also einig sind, dass wir das letzte gesetzte Bit suchen (und wir brauchen nicht einmal die Position, da wir den Teiler selbst suchen, nicht die wievielte Potenz von 2 er ist), dann ist die Magic:

    number ^ (number & (number - 1))
    

    Erklärung, sei number = xxxx1000, xxxx beliebig, Anzahl 0 beliebig:

    1. (number - 1) macht aus xxxx1000 ein xxxx0111
    2. (number & (number - 1) ist also xxxx1000 & xxxx0111, also insgesamt xxxx0000
    3. number ^ (number & (number - 1)) ist dann xxxx1000 ^ xxxx0000, also 00001000, unser gesuchtes Ergebnis

    PS: https://ideone.com/C5wLyv
    PPS: Geht schönerweise auch für Null und negative Zahlen auf, wobei das zugegebenermaßen gar nicht bewusst so entworfen wurde. Viel Spaß, das deinem Lehrer zu erklären!



  • Dann können wir auch machen:
    auto ergebnis = 1ll << __builtin_ctzll(number)
    Hat noch den Vorteil, dass 1ll wie 111 aussieht 😉


  • Mod

    Für so etwas exotisches gibt es Builtins!? Wie kennt man so etwas?



  • @SeppJ sagte in Größte Zweierpotenz:

    Wie kennt man so etwas?

    google.

    PS: ich finde deine Lösung schöner, aber würde hier beim Lernen wohl meine erste Lösung einreichen, weil man damit for und % übt und sie leicht für andere Aufgaben abänderbar ist.
    Edit2: außerdem geht die count-trailing-zero-Bit-Funktion nicht für 0 (da kommt dann 64 raus - oder ist, je mehr man nachforscht, ggf. sogar undefiniert oder implementation-defined).



  • @wob sagte in Größte Zweierpotenz:

    int groesstePotenz = 1;

    Vielen Dank an alle!


Log in to reply