Implementierung Horner-Schema in WHILE-Schleife zur Umrechnung von INT nach HEX

Was macht ihr denn da: das Horner-schema handelt vom ausklammern bei polynomen (früher hat man damit rechenoperationen gespart, heute kennt das kein Schwein mehr)

3x^2+5x+1=(3x+5)*x+1

a[3]x^3+a[2]x^2+a[1]x+a[0]=(a[3]x^2+a[2]x+a[1])*x+a[0]

jetzt kann man in der klammer nochmal x ausklammern (das macht man solange wie es geht …)

((a[3]x+a[2])*x+a[1])*x+a[0]

Den Wert eines Polynoms so auszurechnen nennt man das Horner-Schema, hier anzuwenden mit x = 16

    	char[] koeff = hex.toUpperCase().toCharArray();
    	int summe = 0;
    	int index = 0;
    	while(index<koeff.length){
    		summe = summe * 16 + (koeff[index] - (koeff[index]<'A' ? 48 : 55));
    		index++;
    	}
    	return summe;
    }
    ```

[quote=Bleiglanz]beginne mit i=Stellenanzahl
summe=0
solange(i>=0)
summe = summe * x + a[i–]

oder so ähnlich[/quote]
Das ist ja das, was @Timothy_Truckle in ausführlicher Form hier geschrieben hatte.
Wobei bei i = 0 begonnen und i inkrementiert statt dekrementiert werden muss (most significant nibble kommt schließlich zuerst). Edit: hatte deine Indizierung falsch herum gelesen. Das Dekrement ist korrekt.

Ja, siehe Zeile 25 bis 41. dez = dez.multiply(BigInteger.valueOf(16)); kann auch einfach davor geschrieben werden, denn 0*16 ist ja 0. und wenn da wirklich keine komischen Zeichen drin sind, dann if kleiner 9 elseif kleiner F elseif f else reicht. (So viel traue ich dem Zigarrenmann schon zu.)

[QUOTE=cmrudolph]Das ist ja das, was @Timothy_Truckle in ausführlicher Form hier geschrieben hatte.
Wobei bei i = 0 begonnen und i inkrementiert statt dekrementiert werden muss (most significant nibble kommt schließlich zuerst). Edit: hatte deine Indizierung falsch herum gelesen. Das Dekrement ist korrekt.[/QUOTE]

Sorry, hatte ich glatt überlesen dass Timothy das schon superausführlich erklärt hatte

Das Dekrement ist doch nicht korrekt (hab das oben schon korrigiert), beim einem toCharArray kriegt man ja im index 0 schon die höchste Stelle :slight_smile:

Daher kam meine Verwirrung. Allerdings hattest du bei der „Herleitung“

den Index andersherum definiert :wink: Deshalb passte das schon zu deinem Pseudocode.

Ich hab’ das mal umgeschrieben (nach meinem Nachmittagsschläfchen):

 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

/**
 * @author CB (Letztfassung {f})
 */
public class HexNachDezi {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Zeichen (in Form \"\\uXxXx....\"): ");
        String line = br.readLine();
        //if (!line.matches("^\\\\u[0-9A-Fa-f]{4,}$")) {
        //    throw new IllegalArgumentException(
        //            "Sie sind leider zu bloed, [0-9A-Fa-f]{4,} einzugeben.");
        //}
        String hex = line.substring(2); //IOOBE wenn len <= 1
        BigInteger dezi = BigInteger.ZERO;
        for (int i = 0; i < hex.length(); i++) {
            char c = hex.charAt(i);
            dezi = dezi.shiftLeft(4);
            if (c >= '0' && c <= '9') {
                dezi = dezi.or(BigInteger.valueOf(c - '0'));
            } else if (c >= 'A' && c <= 'F') {
                dezi = dezi.or(BigInteger.valueOf(c - ('A' - 10) ));
            } else if (c >= 'a' && c <= 'f') {
                dezi = dezi.or(BigInteger.valueOf(c - ('a' - 10) ));
            } else {
                throw new IllegalArgumentException(
                        "Sie sind leider zu bloed, [0-9A-Fa-f]{4,} einzugeben.");
            }
        }
        System.out.println("lin = " + line);
        System.out.println("hex = " + hex);
        System.out.println("dez = " + dezi);
        if (dezi.compareTo(BigInteger.valueOf(0xffff)) > 0) {
            System.out.println("Ihre Eingabe ist leider kein Unicode-Zeichen.");
        } else {
            System.out.println("chr = " + (char) dezi.intValue());
        }
    }
}```

Multiplikation ist ja immer etwas zeitkritisch, daher Shift und Or (bitweise), welche hoffentlich nicht zeitkritisch sind.

([Edit: Ein boolean-{/byte-/char-}Array mit n*4 Plätzen wäre whrs. besser für diese Aufgabe.])

dez heißt jetzt dezi, die Literal-Konstante 0xffff eingesetzt, dezi.intValue() verwendet.


run:
Zeichen (in Form “\uXxXx…”): \uFfFfFfFf
lin = \uFfFfFfFf
hex = FfFfFfFf
dez = 4294967295
Ihre Eingabe ist leider kein Unicode-Zeichen.
BUILD SUCCESSFUL (total time: 20 seconds)



(Keine Panik hier, das Programm hat nicht 20 Sekunden nur gerechnet - solange brauche ich immer, um mir eine sinnvolle Eingabe auszudenken :( )

Und, wer von euch hat so viele Euronen auf seinem Konto?$?$

[quote=CyborgBeta]Multiplikation ist ja immer etwas zeitkritisch, daher Shift und Or (bitweise), welche hoffentlich nicht zeitkritisch sind.[/quote]Viel Kritischer ist premarture optimization!

bye
TT

Mhm, so ein blödes Argument kommt immer, wenn mein Programm ausgereift ist und/oder es andere nicht verbessern wollen oder können.

Geh’ mal weiter Segelflieger aus Papier basteln. :smiley: (Ironisch-scherzhaft)

BigInteger. Performance. 'nuff said.

BigInteger.valueOf(c - ‘0’)
BigInteger.valueOf(c - (‘A’ - 10) )
und
BigInteger.valueOf(c - (‘a’ - 10) )

wird mit den Werten 0…15 aufgerufen. Damit nicht jedes Mal ein neues Objekt erstellt werden muss, können diese im Cache liegen. Dafür, das BigInteger generell langsam ist, viel Speicherplatz verbraucht oder nicht besser implementiert werden kann, kann ich nix.

Der TO hat jetzt:

  • einen Ansatz mit while-Schleife, Horner-Schema (Multiplikation mit 16/left shift um 4, Addition der Hexadezimalstelle/Or),
  • die Herleitung/induktive Definition: a16^2+b16^1+c*16^0=(16(16(a)+b)+c) (ersetze a bis c durch b bis d, ersetze b durch 16(a)+b usw.),
  • mal ansatzweise einen regulären Ausdruck,
  • den Umgang mit Ausnahmen/Exceptions,
  • die Ein-/Ausgabe mit BufRed,
  • den Wertebereich von char, int, long usw.

Was will er/sie/Ihr denn noch?