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;
-
-
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 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.
-
Ist die Frage nicht äquivalent dazu, die "Nullen" rechts in der Binärdarstellung zu zählen?
-
@SeppJ yay
-
Dann Folgeaufgabe: größte Dreierpotenz!
-
-
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:
(number - 1)
macht aus xxxx1000 ein xxxx0111(number & (number - 1)
ist also xxxx1000 & xxxx0111, also insgesamt xxxx0000number ^ (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, dass1ll
wie111
aussieht
-
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).
-