Berechnen Sie die Anzahl der Zeiten, der durch zwei teilen

Grüße.

Ich habe eine java-Methode, die ich als teuer, und ich bin versucht zu ersetzen, einige Anrufe, um es mit einem mathematischen Ausdruck. Problem ist, ich bin Scheiße in Mathe. Ich meine wirklich saugen.

Folgende sollte erklären, die Muster, die ich versuche zu nutzen.

f(x)   -> y
f(x*2) -> f(x)+1

Ist, wenn ich den doppelten Wert für x der Wert für y wird 1 größer als für x/2.
Hier sind einige Beispiel-Ausgabe:

f(5)   -> 6
f(10)  -> 7
f(20)  -> 8
f(40)  -> 9
f(80)  -> 10
f(160) -> 11
f(320) -> 12

Mein Aktueller Ansatz ist brute-force. Wechsele ich über die X-und testen Sie, wie viele Male kann ich halbieren, bevor ich es erreichen, 5, und schließlich habe ich Sie 6. Das funktioniert und ist schneller als der Aufruf der original-Methode. Aber ich war auf der Suche nach einer "eleganten" oder potenziell billigere Lösung.

Akzeptierte Antwort geht an den einen, der es schafft, mir zu helfen, ohne Hinweis darauf, wie dumm ich bin 🙂

(der Titel wahrscheinlich saugt, weil ich nicht weiß, was ich Suche)

was ist f(0), f(1), f(2) f(3) f(4)?
In Ihrem Beispiel, was würden Sie definieren f(6) als Entsprechung von (zum Beispiel). Oder ist Ihre Funktion nur gültig für die Werte von x sind insbesondere ein Vielfaches von Ihr ab x?
Das klingt wie einige seltsame Arsch Logarithmus.
Tut f(15) = 16?
f(0) ist illegal. f(1)=4, f(2)=2, f(3)=8, f(4)=3
f(15) = 18

InformationsquelleAutor Ronnis | 2010-12-20

6

Haben Sie sich überlegt, dass das, was Sie sehen, ist im wesentlichen eine Division durch fünf, zu finden, was die macht der zwei, die Sie haben, und fügen Sie 6, um diese macht?

Den Allgemeinen Ansatz "gegeben Y finden Sie heraus, was macht X es ist" ist die Verwendung Logarithmen. Mit einem Rechner versuchen, die Aufteilung der Logarithmus von 64 mit dem Protokoll 2 und sehen, dass Sie bekommen 6.

So dividieren durch fünf, nehmen Sie das Protokoll, geteilt durch den log von zwei, und fügen Sie sechs.
- Wie ich es verstehe, gab er 5 als Beispiel. Es kann eine beliebige ungerade Zahl ist. Also im Grunde braucht er ein x als x*2^n, wobei x ist eine beliebige ungerade Zahl ist.
- Verpasste "Beispiel" in der Frage. Verstanden zu werden, die Werte.
- örn. Ja habe ich schon gedacht, aber ich wusste nicht wie man das macht 2.
- wo haben die "jede ungerade Zahl" aus?
- ørn, er teilt sich durch zwei, in einer Schleife, bis es unmöglich ist, mehr. Eine Zahl, die unmöglich ist, eine Division durch zwei ist eine ungerade Zahl. Wenn x eine gerade Zahl ist, Sie könnten dies tun: x*2^n = (x/2)*2^(n+1).
InformationsquelleAutor Thorbjørn Ravn Andersen
3

Du suchst einen Logarithmus (Basis 2)

wenn die Basis x ist 5, und die Basis y 6 ist, dann log2(320 /5) + 6 = 12

In Java (Math.log(320 /x) /Math.log(2)) + y

Wo x und y sind die ursprünglichen Werte (in diesem Beispiel f(5) = 6)
- Dies ist wahrscheinlich das, was ich Suche
- wie werden Sie gehen, um herauszufinden, die base x? Auch ich bin mir nicht sicher, ob mit dem Doppel-based Math.melden Sie wird effizienter sein als die Division durch 2 in einer Schleife (eine Verschiebung um ein bit, wirklich).
- gute Punkte. Vielleicht ist die Kosten-von der Suche nach der Basis und anwenden der log-hack ist größer als die Kosten von nur Halbierung der Zahl in einer Schleife.
InformationsquelleAutor Knio
1

was du suchst, ist die Anzahl der Ziffern in der binären Darstellung, die (für eine base-10-Zahl und Logarithmen zur Basis 10) ist gegeben durch log(x)/log(2)
- Die Beispiele, die er gibt, darauf hindeuten, dass er nicht auf der Suche für die Anzahl der Ziffern in der binären Darstellung, weil dann alle von Ihnen wäre falsch.
- stimmt, aber ich hab lieber eine Antwort auf die "Teile durch zwei" - Abschnitt, und lassen Sie das original-poster füllen die Lücken. Beachten Sie, dass mehrere Antworten aufgedreht um die gleiche Zeit 🙂
InformationsquelleAutor David O'Meara

Dies ist keine Antwort, aber ich schaffte es nicht einen Kommentar. Betrachten Sie eine rekursive Funktion:

int someFunc(int n, int times) {
  if(n == 0) return 0;
  if( n % 2 == 0) return someFunc(n/2, times+1);
  else return n+times;
}

Tut es das, was Sie wollen?

someFunc(1, 0) -> 1
someFunc(2, 0) -> 2
someFunc(3, 0) -> 3
someFunc(5, 0) -> 5
someFunc(10, 0) -> 6
...

InformationsquelleAutor khachik

1

First off, Ihre Frage ist nicht gut gestellt. Dies ist ein Beispiel, wie eine Frage sollte nicht gestellt werden (keine straftat). Ich will, dass Ihre Frage ist: gegeben eine positive ganze Zahl x, finden Sie ganze zahlen m, n derart, dass x = m*2^n, wobei m ungerade ist, dann wieder y = f(x) = n + g(m). Denn Sie sagen nicht, wie f(x) errechnet sich für ungerade x, ich nehme an, g(.) gegeben ist.

Wenn in Ihrem problem, n ist nicht groß, es gibt keinen wirklichen nutzen mit einem ausgeklügelten Algorithmus, als eine einfache Schleife (naiver Algorithmus). Ich Stelle ein Algorithmus, der die Vorteile der Fall, wenn n groß ist (sagen wir ein paar hundert, ein paar tausend). Ich weiß nicht, Java, damit ich den Algorithmus in allgemeiner form (unter Verwendung von Python-syntax).

Wenn man die binäre Darstellung von x (b_{N-1} ... b_1 b_0, b_i = 0 oder 1) dann ist dein problem reduziert sich auf finden des ersten bit-1 von rechts (D. H. die am wenigsten signifikanten bit 1). Sagen, dass die position dieses bit ist k (0<=k<=N-1) dann ist n = k und m = x >> k. Ich glaube, das beste, was Sie tun können, um zu finden, k ist die binäre Suche, die Ergebnisse in O(log N) - Algorithmus. Der Algorithmus ist wie folgt (<< und >> sind die shift-Operatoren):
```
Algorithm: Input: x -> Outputs: (m, n)

if x is odd or x == 0: return (x, 0)  # x is odd when x & 1 == 1 or x % 2 == 1
N = ceil(log(x, 2))  # ceil: smallest integer larger than the argument
n = 0
orig_x = x

while x & 1 == 0:   # if bit 0 is 1 (i.e. x is odd), stop the search
  half = int(N/2)
  lowerhalf = x & ((1 << half) - 1)  # obtain the lower half
  if lowerhalf == 0:   # all zeros
    n += half
    x = x >> half
    N -= half
  else:
    x = lowerhalf
    N = half

return (orig_x >> n, n)
```
Als ein Beispiel, wenn N = 1000 (x 1000-bit-Ganzzahl), dieser Algorithmus dauert höchstens 10 Iterationen (während der naive Algorithmus nimmt 1000 Iterationen im schlimmsten Fall). Allerdings tatsächliche Ausführungszeit hängt davon ab, wie die bit-Operationen und = = - operator implementiert werden, der für ganze zahlen von 1000 bit Länge.
- Ich denke, ich habe einen ziemlich guten job zu erklären, was ich nach war, wenn man bedenkt, dass ich nicht wusste, was ich war, nach. Es wurden 6 Antworten in weniger als 20 Minuten, nachdem die Frage gepostet wurde. Das Internet ist voll von Sachen geschrieben, nur die Art und Weise Sie schrieb Ihre Antwort. Es geht über meinem Kopf. Somit ist es nutzlos für mich. Oh, und herzlich willkommen auf stackoverflow!
- vielen Dank für Ihre Begrüßung. Und sorry, dass das Internet voll ist von dem Zeug wie ich schon schrieb, aber man findet Sie nutzlos, weil es zu schwierig für Sie.
InformationsquelleAutor Truong
0

Erstmal OK aus-wir werden bemerken, dass alle Eingänge sind Vielfache von 5, also ziehen wir einen Faktor von 5 in die Eingänge; und wir bemerken, dass die Ausgänge beginnen bei 6, so ziehen wir eine Skalierung durch die 6 Ausgänge. Ich nenne diese neue Funktion g:
```
g(1)      0
g(2)      1
g(4)      2
g(8)      3
g(16)     4
g(32)     5
g(64)     6
```
Nun diese Funktion ist hoffentlich viel mehr vertraut - g(x) ist einfach 2 die macht der x. Und um dies zu tun (in Java), können wir nur verwenden java.lang.Math.pow(2, x).

Alles, was bleibt, ist f aus g. Aber das ist einfach:
- gegeben, den Eingang zu f
- Division durch 5
- als Eingabe für g
- hinzufügen 6
Werde ich verlassen für Sie.

InformationsquelleAutor AakashM
-1

Versuchen Sie dies:
```
f(x) = log<sub>2</sub>(x/5) + 6
```
- Ernsthaft? Keinen weiteren Kommentar? Keine Erklärung warum? Sie können tun, besser als Sie! -1 für Sie.
InformationsquelleAutor aartist

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.