/**
 * class Binaerrechner - erlaubt Konversion von Binaer- und natuerlichen Zahlen
 * sowie elementare Rechenoperationen
 * Nur fuer Zahlen im Groessenbereich von [int].
 * 
 * @author MB
 * @version MAR 2018
 */
public class Binaerrechner
{
    
    /**
     * Constructor for objects of class Binaerrechner
     */
    public Binaerrechner()
    {
       
    }
    
    /**
     * Methode rechnet eine Binaerzahl in eine Dezimalzahl um;
     * ohne Test auf Beschraenktheit der [int]-Groesse
     */
    public int binaerInDezimal(Binaerzahl b){
        String bits = b.gibBitfolge();
        int laenge = bits.length();
        int output = 0;
        int exponent = 0;
        // die Zahl wird von rechts nach links gelesen und stellenweise ausgewertet
        for(int i = 1; i <= laenge; i++, exponent++){
            if(bits.charAt(laenge-i) == '1'){
                output += zweierpotenz(exponent);
            }
        }
        return output;
    }
    
    /**
     * Methode rechnet eine positive Dezimalzahl vom Typ [int] in eine Binaerzahl um.
     * @param - die umzurechnende Dezimalzahl
     * @return - die Binaerzahl 
     */
    public Binaerzahl dezimalInBinaer(int a){
        // Methode nur fuer positive Zahlen
        if(a < 0){
            return null;
        }
        // Vorwegnehmen der elementarsten Faelle
        else if(a == 0){
            return new Binaerzahl("0");
        }
        else if(a == 1){
            return new Binaerzahl("1");
        }
        else{
            int laenge = bestimmeHoechsteZweierpotenz(a);  // mehr vordere Stellen braucht die Binaerzahl nicht
            char[] bitfolge = new char[laenge+1]; // aber eine zusaetzliche fuer [2 HOCH 0]
            bitfolge[0] = '1'; // die erste Stelle ist immer '1'
            int abzug = zweierpotenz(laenge); // [laenge] entspricht der festgestellten Zweierpotenz
            int rest = a - abzug; // der auszuwertende Rest
            // Auffuellen der restlichen Bits von links nach rechts!
            for(int i = 1; i <= laenge; i++){ // [laenge] ist um 1 kleiner als die tatsaechliche Laenge (s.o.)
                if(zweierpotenz(laenge-i) <= rest){ // in diesem Fall muss diese Zweierpotenz addiert werden
                    bitfolge[i] = '1';
                    rest = rest - zweierpotenz(laenge-i);
                }
                else { // in diesem Fall wird diese Zweierpotenz nicht benoetigt
                    bitfolge[i] = '0';
                }
            }
            return new Binaerzahl(new String(bitfolge));
        }
    }
    
    /**
     * Die folgenden beiden Methoden realisieren die Grundrechenarten Addition und Multiplikation fuer
     * Binaerzahlen, indem diese ueber die Umwandlung in natuerliche Zahlen auf die entsprechenden 
     * Operationen dort zurueckgefuehrt werden.
     */
    public Binaerzahl addieren(Binaerzahl b1, Binaerzahl b2){
        return dezimalInBinaer(binaerInDezimal(b1) + binaerInDezimal(b2));
    }
    
    public Binaerzahl multiplizieren(Binaerzahl b1, Binaerzahl b2){
        return dezimalInBinaer(binaerInDezimal(b1) * binaerInDezimal(b2));
    }
    
    /**
     * Die Methode bestimmt zu einer Zahl die hoechste Zweierpotenz, die kleiner als diese Zahl ist
     * @param - die zu pruefende Zahl
     * @return - der Exponent der entsprechenden Zweierpotenz
     */
    private int bestimmeHoechsteZweierpotenz(int a){
        int output = 1; // Fall [0] kann hier nicht mehr auftreten (s.o.)
        while(zweierpotenz(output) <= a){
            output++;
        }
        return output-1; // denn im letzten Durchgang wurde der Exponent zu Unrecht erhoeht
    }
    
    /**
     * Methode berechnet Zweierpotenzen im [int]-Bereich
     * @param - der Exponent
     * @return - die Zweierpotenz
     */
    private int zweierpotenz(int exponent){
        int output = 2;
        if(exponent == 0){
            return 1;
        }
        else{
            while(exponent > 1){
                output = output * 2;
                exponent--;
            }
            return output;
        }
    }
    
    /**
     * Addieren von Binaerzahlen ausgehend von deren Repraesentation als Bitfolge in Strings.
     */
    public Binaerzahl direktesAddieren(Binaerzahl b1, Binaerzahl b2){
        int b1Laenge = b1.gibBitfolge().length();
        int b2Laenge = b2.gibBitfolge().length();
        // Zunaechts muss die groesse Laenge ermittelt werden, um genug Stellen zum Addieren bei der kleineren Zahl zu haben
        int laenge = b1Laenge;
        if(b1Laenge < b2Laenge){
            laenge = b2Laenge;
        }
        // zum Addieren werden [int]-Arrays benutzt, da diese mit [0] initialisiert werden
        int[] b1Zahlen = new int[laenge];
        int[] b2Zahlen = new int[laenge];
        int[] summe = new int[laenge+1]; // wegen Uebertrag bedarf es einer weiteren Stelle
        // die beiden Stellvertreter-Arrays werden befuellt, von rechts nach links
        for(int i = 1; i <= laenge; i++){
          if(i <= b1Laenge && b1.gibBitfolge().charAt(b1Laenge-i) == '1'){
              b1Zahlen[laenge-i] = 1;
          }
          if(i <= b2Laenge && b2.gibBitfolge().charAt(b2Laenge-i) == '1'){
              b2Zahlen[laenge-i] = 1;
          }
        }
        // jetzt wird addiert mit Uebertrag von rechts nach links; es muessen 8 Faelle unterschieden werden
        boolean uebertrag = false;
        for(int i = laenge-1; i >= 0; i--){
            if(b1Zahlen[i] == 1 && b2Zahlen[i] == 1 && uebertrag){
                summe[i+1] = 1; // [i+1] da dieses Array ja eine Position mehr hat
            }
            else if (b1Zahlen[i] == 1 && b2Zahlen[i] == 1){
                summe[i+1] = 0;
                uebertrag = true;
            }
            else if (b1Zahlen[i] == 1 && b2Zahlen[i] == 0 && uebertrag){
                summe[i+1] = 0;
            }
            else if (b1Zahlen[i] == 1 && b2Zahlen[i] == 0){
                summe[i+1] = 1;
            }
            else if (b1Zahlen[i] == 0 && b2Zahlen[i] == 1 && uebertrag){
                summe[i+1] = 0;
            }
            else if (b1Zahlen[i] == 0 && b2Zahlen[i] == 1){
                summe[i+1] = 1;
            }
            else if (b1Zahlen[i] == 0 && b2Zahlen[i] == 0 && uebertrag){
                summe[i+1] = 1;
                uebertrag = false;
            }
            else if (b1Zahlen[i] == 0 && b2Zahlen[i] == 0){
                summe[i+1] = 0;
            }
        }
        if(uebertrag){
            summe[0] = 1;
            laenge++; // fuer das Weitere
        }
        // die Summe wird nun in ein [char]-Array geschrieben
        char[] bitfolge = new char[laenge];
        for(int i = 0; i < laenge; i++){
           bitfolge[i] = (summe[i]>0) ? '1' : '0';
        }
        return new Binaerzahl(new String(bitfolge));
    }
    
    
}

class Binaerzahl
{
    private final String bitfolge; // die Bitfolge darf sich nie aendern

    /**
     * Constructor for objects of class Binaerzahl
     */
    public Binaerzahl(String bits)
    {
        bitfolge = bits;
    }

    public String gibBitfolge(){
        return bitfolge;
    }
}