Größte Zweierpotenz
-
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).
-