Methoden Logarithmus zur Basis 2

[DerDecane]

Hey Leute, ich arbeite in Java gerade an einem Umrechner von Dezimalzahlen in Binärschreibweise. Funktioniert soweit alles, hatte anfangs die Länge des Arrays in der die Binärzahl gespeichert ist auf 10 gesetzt (nur für Testzwecke). Wollte jetz allerdings die Länge des Arrays an die benötigte Länge anpassen (z.B. benötigt die Zahl 7 im Array 3 Stellen, und die Zahl 2 nur 2 Stellen).

Das rechnet man ja mit dem Logarithmus Dualis aus. Meine (zugegeben etwas wirre) Methode dafür sieht im Moment so aus:

static int logarithmus (int x){
        double log = Math.log(x)/Math.log(2.0);
        double zahl = Math.ceil(log);
        int zahlerg = (int)(zahl);
        return zahlerg;
    }

Allerdings gibt's bei der Ausgabe z.b. bei 4 nur 2 Stellen aus obwohl ich da 3 benötige. Bei der Zahl 7 funktionierts allerdings und gibt mir die benötigten 3 Stellen aus. Wo istn da ein Fehler ich bin ehrlichgesagt überfragt ^^

 

[Meniskusschaden]

Na ja, der log_2(4) ist nun mal zwei, denn 2^2 = 4. Dein Denkfehler ist vermutlich, dass man mit zwei Bit vier Werte abbilden kann. Das sind dann aber die Zahlen von 0 bis 3. Du könntest vielleicht floor(x+1) statt ceil(x) schreiben. Dann würde ich die Methode aber nicht mehr logarithmus nennen.

 

[CSHW89]

Mathematisch korrekt (ohne Rundungsfehler s.u.) wäre es, wenn du am Anfang

double log = Math.log(x+1)/Math.log(2.0);

rechnest, also zu x eins dazu addierst.
log_2(3) = 1,58..., du willst 2
log_2(4) = 2, du willst 3
log_2(5) = 2,32..., du willst 3
Also:
ceil(log_2(3+1)) = ceil(2) = 2
ceil(log_2(4+1)) = ceil(2,32) = 3
ceil(log_2(5+1)) = ceil(2,58) = 3

Weshalb ich aber die Rundungsfehler angesprochen hab. Es kann passieren das z.b. bei ceil(log_2(3+1)) etwas rauskommen kann wie ceil(2.00000000001) = 3, dann wäre es wieder falsch.

Verhindern kann man das, indem man die nötigen Stellen anders berechnet. Eine Möglichkeit wäre es, die Zahl solange durch 2 dividieren (Ganzzahldivision), bis die Zahl gleich 0 ist. Die Anzahl der Schritte ist dann die Anzahl nötiger Stellen:
3 / 2 = 1, 1 / 2 = 0 (zwei Schritte)
4 / 2 = 2, 2 / 2 = 1, 1 / 2 = 0 (drei Schritte)
5 / 2 = 2, 2 / 2 = 1, 1 / 2 = 0 (drei Schritte)
Statt durch 2 dividieren, kann man dann auch um eine Stelle binär shiften: "zahl = zahl >> 1". Dies wäre eine Möglichkeit die nötige Länge immer richtig zu bestimmen, und außerdem auch noch performanter als über den Logarithmus.

lg Kevin

 

[Xyz1]

Erst dachte ich, Anfängerfrage, dann hab ich es getestet und folgende Probleme tragen auf:

    private static int anzahlen(long l) {
        if (l < 0) {
            return 64;
        }
        if (l <= 1) {
            return 1;
        }
        return (int) Math.ceil(Math.log(l) / Math.log(2));
    }
// ....
        System.out.println(anzahlen(-1)); // 64
        System.out.println(anzahlen(0)); // 1
        System.out.println(anzahlen(1)); // 1
        System.out.println(anzahlen(4)); // 2
        System.out.println(anzahlen(5)); // 3
        System.out.println(anzahlen(6)); // 3
        System.out.println(anzahlen(7)); // 3
        System.out.println(anzahlen(Integer.MAX_VALUE)); // 31
        System.out.println(anzahlen(Long.MAX_VALUE)); // 63

Nun ja, 4 hat 3 Bit(s) und nicht 2.