How can I use a 4 bit adder and 4 bit identity to create a 4 bit multiplier that multiplies two 4 bit numbers?

[berserkerdq2]

Hi, ich habe zwei Methoden, einmal einen 4-Bit-Addierer, wo ich zwei 4-Bit-Zahlen übergebe. Als Rückgabewert erhalte ich die Addition und ein Carrybit.

Außerdem habe ich eine 4-Bit-Identität, als Methode.

Eine 4-Bit-Identität bedeutet einfach, dass ich 4 Bits an diese Methode übergebe und ein weiteres Bit, wenn das weitere Bit, welches ich mit übergebe, 0 ist, wird 0000 zurückgegeben, aber wenn das Bit 1 ist, gibt die Methode die 4 Bits zurück, die ich der Methode gegeben habe.

Wie kann ich damit einen 4-Bit-Multiplikator erstellen? Ich darf nur diese beiden Methoden verwenden. Keine Schleifen, Bedingungen etc. Ich darf nur die beiden Methoden benutzen und dann deren Rückgabewerte verwenden, die ich auch wieder an die Methoden senden darf.

(Das Ergebnis der Multiplikation muss 8 Bit haben).

Ich verstehe nicht, wie ich nur mit den beiden Methoden das realisieren soll.

(Sorry, dass der Beitragsname auf Englisch ist, mein Browser hatte automatische Übersetzung an)

 

[temi]

Sollen da zwei bestimmte Zahlen multipliziert werden oder zwei Beliebige? Vermutlich Letzteres, aber man kann ja mal sicherheitshalber fragen

 

[berserkerdq2]

Sollen da zwei bestimmte Zahlen multipliziert werden oder zwei Beliebige? Vermutlich Zweiteres, aber man kann ja mal sicherheitshalber fragen

zwei beliebige

 

[temi]

Ich habe grad kurz an eine rekursive Lösung gedacht, um die Schleife zu ersetzen, aber irgend eine Abbruchbedingung braucht es da auch.

 

[httpdigest]

Implementiere einfach die "Binary Long Multiplication" Methode: https://en.wikipedia.org/wiki/Binary_multiplier#Binary_long_multiplication
Du brauchst also (maximal) vier Additionen. Und mit der Identitätsfunktion kannst du das eben als _immer_ vier Additionen implementieren, basierend darauf, ob das jeweilige Bit 0 oder 1 ist.
Du brauchst aber in jedem Fall definitiv Bit-Shift-Operatoren. (<- stimmt nicht, siehe Antwort von @temi unten)

 

[temi]

Du brauchst aber in jedem Fall definitiv Bit-Shift-Operatoren.

Müsste sich ein Links-Shift nicht durch eine Addition mit sich selbst ersetzen lassen? Left-Shift entspricht ja einer Multiplikation mit 2.

 

[Staarfightaar]

Müsste sich ein Links-Shift nicht durch eine Addition mit sich selbst ersetzen lassen? Left-Shift entspricht ja einer Multiplikation mit 2.

ja

 

[temi]

ja

Na, dann sollte jetzt alles zusammen zu bringen sein.

 

[Jw456]

hier das Prinzip auf deutsch

Dualzahlen multiplizieren: Multiplikation von Dualzahlen

 

[berserkerdq2]

Mit shiften etc. bekomme ich das auch hin, aber ich darf das alles nicht verwenden. Mit shiften war eine Aufgabe vorher, die war noch in Ordnung. Jetzt dürfen wir nur noch die beiden Methoden verwenden, nichts anderes mehr. Also kein shiften, keine Schleifen, keine Ifs, nur die beiden Methoden und deren Rückgabewerte.

(Mein Problem ist eher, wie komme ich auf die 8 Bits? Ich führe die Additionen durch und erhalte ja die carrybits und die 4 Bits, die nach der Addition entstanden sind, wie füge ich die dann zsm?)

 

[temi]

Mit shiften etc. bekomme ich das auch hin, aber ich darf das alles nicht verwenden. Mit shiften war eine Aufgabe vorher, die war noch in Ordnung. Jetzt dürfen wir nur noch die beiden Methoden verwenden, nichts anderes mehr. Also kein shiften, keine Schleifen, keine Ifs, nur die beiden Methoden und deren Rückgabewerte.

(Mein Problem ist eher, wie komme ich auf die 8 Bits? Ich führe die Additionen durch und erhalte ja die carrybits und die 4 Bits, die nach der Addition entstanden sind, wie füge ich die dann zsm?)

Warum lässt du uns dann rätseln, wenn dir fast alles klar ist? Du hättest ja gleich den Ansatz und das konkrete Problem benennen können. Zum Shift, steht ja weiter oben schon etwas.

Edit: Wie werden die 4 Bit denn überhaupt verwaltet? Es gibt ja keinen expliziten Typen in Java dafür.

 

[berserkerdq2]

Warum lässt du uns dann rätseln, wenn dir fast alles klar ist? Du hättest ja gleich den Ansatz und das konkrete Problem benennen können. Zum Shift, steht ja weiter oben schon etwas.

Naja, weil ich ehrlich gesagt keine Ahnung habe, wie ich hier vorgehen soll.

Beispiel:

Ich habe 1010 x 1011

jetzt kann ich mit der identity Methode mir die Werte hollen dann hätte ich als Addition:

1010
+0000
+1010
+1010

Jetzt ist mein Problem, wie gehe ich weiter vor? Weil so die zu addieren, macht ja wenig sinn? Oder?

 

[Jw456]

eine 8 bit Variable Akkumulator darfst du doch verwenden.

 

[berserkerdq2]

eine 8 bit Variable Akkumulator darfst du doch verwenden.

Was genau ist ein 8 bit variabler akkumulator?

 

[temi]

Edit: Wie werden die 4 Bit denn überhaupt verwaltet? Es gibt ja keinen expliziten Typen in Java dafür.

Der Edit ist evtl. untergegangen...

 

[httpdigest]

Du brauchst halt einen Java Datentypen, der mindestens 8 Bit hat. Das kann halt z.B. einfach ein byte sein.

 

[berserkerdq2]

Du brauchst halt einen Java Datentypen, der mindestens 8 Bit hat. Das kann halt z.B. einfach ein byte sein.

Bei uns ist es so, dass wir die Bits als String übergeben und die Rückgabewerte sind auch Strings, also das Carrybit, sowie auch die 4 Bits. Also der Addierer erhält 4 bits als String 2x und addiert die und gibt das Ergebnis als String zurückl und den Carrybit auch

 

[httpdigest]

Bei uns ist es so, dass wir die Bits als String übergeben und die Rückgabewerte sind auch Strings, also das Carrybit, sowie auch die 4 Bits

Wenn du eh Strings verwendest, was ist dann jetzt genau das Problem? Ein String kann ja beliebig lang sein.

 

[berserkerdq2]

Wenn du eh Strings verwendest, was ist dann jetzt genau das Problem? Ein String kann ja beliebig lang sein.

Mein Problem ist wie nutze ich die Rückgaben? Das verstehe ich nicht? Was fange ich mit den Carrybits, die ich erhalte etc. an?

Beispiel bei 1010*1011:

1010
+0000
+1010
+1010

Dass ich das jetzt addieren muss, ist mir klar, aber wie gehe ich vor?

Als erstes addiere 1010+0000, mit den addierer, dann, nehme ich 1010 und addiere es mit sich selber 2x oder? damit ich zweimal shifte, dann addiere ich das ergebnis von 1010+0000 mit dem geshifteten oder? Aber ich erhalte doch jetzt auch ein Carrybit, was fange ich damit an?

 

[Staarfightaar]

was meinst ud mit carrybit?

 

[berserkerdq2]

was meinst ud mit carrybit?

Mein Problem ist, wenn ich den 4 bit addierer nutze, erhalte ich die addierten Bits zurück und den Übertragsbit, muss ich den Übertragsbit überhaupt nutzen?

 

[Staarfightaar]

ich weis halt nicht was du überhaupt mit übertragungsbit meinst... was soll das sein?

das vorzeichen ist in der bitzahl gespeichert

 

[temi]

ich weis halt nicht was du überhaupt mit übertragungsbit meinst... was soll das sein?

das vorzeichen ist in der bitzahl gespeichert

https://de.wikipedia.org/wiki/Übertragsbit

 

[Jw456]

Mein Problem ist wie nutze ich die Rückgaben? Das verstehe ich nicht? Was fange ich mit den Carrybits, die ich erhalte etc. an?

Beispiel bei 1010*1011:

1010
+0000
+1010
+1010

Dass ich das jetzt addieren muss, ist mir klar, aber wie gehe ich vor?

Als erstes addiere 1010+0000, mit den addierer, dann, nehme ich 1010 und addiere es mit sich selber 2x oder? damit ich zweimal shifte, dann addiere ich das ergebnis von 1010+0000 mit dem geshifteten oder? Aber ich erhalte doch jetzt auch ein Carrybit, was fange ich damit an?

stimmt leider nicht . Der Vergleich geht von hinten los

     1010
    1010
   0000
  1010  
  1101110

 

[temi]

addiere es mit sich selber 2x oder? damit ich zweimal shifte

Mit sich selbst addieren ist einmal shiften nach links.

 

[Staarfightaar]

0000.0000 <= ergebnisspeicher

// prinzipielle addition
// dein speicher hat aber 8 bits frei also erweitern
1100 +
1101

    also
0000.1100
0000.1101
---------
0001.1001 <= wird returned

sobald du dann multiplikation hast

X * Y

hast du ja X+ X+X und das Y mal.. das heißt

while(rechneMinus1(Y) != 0)
{
    addiereMitSichSelbst(X);
}

 

[Staarfightaar]

Mit sich selbst addieren ist einmal shiften nach links.

aber du hast dann

4 * 4

    4 + 4 = 8 // nach shift
        8 + 8 = 16 // nach zweiten shift
            16 +16 = 32 // nach dritten shift
                32 + 32 = 64 // nach vierten shift

 

[temi]

0000.0000 <= ergebnisspeicher

// prinzipielle addition
// dein speicher hat aber 8 bits frei also erweitern
1100 +
1101

    also
0000.1100
0000.1101
---------
0001.1001 <= wird returned

sobald du dann multiplikation hast

X * Y

hast du ja X+ X+X und das Y mal.. das heißt

while(rechneMinus1(Y) != 0)
{
    addiereMitSichSelbst(X);
}

Was soll diese Antwort jetzt bringen?

 

[temi]

muss ich den Übertragsbit überhaupt nutzen?

Ja natürlich, das ist bei der 4 Bit Addition, das 5. Bit, wenn das Ergebnis nicht mehr in die 4 Bit passt.

 

[Staarfightaar]

Was soll diese Antwort jetzt bringen?

was soll dir der shift bringen bei der multiplikation ?

 

[temi]

was soll dir der shift bringen bei der multiplikation ?

Mein Tipp: Lies das Thema mal konzentriert durch, dann wirst du das verstehen. Insbesondere Beiträge #1 #5 #6

 

[Staarfightaar]

 4-Bit-Addierer, wo ich zwei 4-Bit-Zahlen übergebe.

was willst du davon shiften? 2 bit zahlen sollen addiert werden

 

[Jw456]

Frage zu deiner Adder Methode stellt das ein Full-Adder oder nur ein Halb-Addar dar?

Bei Full wäre es ja einfach um auf 8Bit zukommen einfach hintereinander schalten.

 

[berserkerdq2]

Frage zu deiner Adder Methode stellt das ein Full-Adder oder nur ein Halb-Addar dar?

Bei Full wäre es ja einfach um auf 8Bit zukommen einfach hintereinander schalten.

Ist ein Fulladder, habe trotzdem keine Ahnung wie ich auf die 8 komme, wenn ich die hintereinander schachtele.

 

[Jw456]

Zeige wal wie die Methode aussehen. Was übergeben wird Datentyp und was zurück geben wird Datentyp Vielleicht ein Beispiel. Du sagst es sind Strings also ein Beispiel wie die Strings ausschauen.

Full Adder würde heißen zwei 4 Bit Zahlen plus ein Übertrag als Eingang und eine 4Bit Zahl plus Übertrag als Ausgang.
Ohne den Übertrag Eingang ist es ein halb Adder.

 

[berserkerdq2]

Zeige wal wie die Methode aussehen. Was übergeben wird Datentyp und was zurück geben wird Datentyp Vileicht ein Beispiel. Du sagst es sind Strings also ein Beispiel wie die Strings ausschauen.

Full Adder würde heißen zwei 4 Bit Zahlen plus ein Übertrag als Eingang und eine 4Bit Zahl plus Übertrag als Ausgang.

Hi, die Methoden darf ich leider nicht sharen, würde das sonst posten.

Es ist so, dem Addierer für 4 Bits, übergibt man:

zwei Strings, die jeweils 4 Bits enthalten

und zurück erhält man:
- einen String mit 4 Bits und
- einen String mit dem Carrybit.

(Ist dann wohl ein Halbaddierer, sorry)

 

[Jw456]

Ein Beispiel von einem Eingabe String ein Ausgabe reicht.

 

[berserkerdq2]

Ein Beispiel von einem Eingabe String ein Ausgabe reicht.

Stirng eingabe1 = "1010";

String eingabe2 = "1110";

//man übergibt zwei String, die addiert werden.

String[] ergebnis = VierBitAddierer(eingabe1, eingabe2);

//Im Array ist der erste String 4 Bit lang und beim zweiten String ist nur das Carrybit und das wars, also der Array hat nur die zwei Werte, ist der Rückgabewert der Methode VierBitAddierer

 

[Jw456]

ok dachte ich mir das es ein String Array ist und kein Array

 

[berserkerdq2]

ok dachte ich mir das es ein String Array ist und kein Array

Diese Identitymethode übergibt man auch zwei String

Identität(String1, String2)

String1 ist ein String mit den 4 Bits und String2 muss 0 oder 1 sein, wenn es 0 ist erhalte ich als Rückgabewert 0000 und wenn es 1 ist, erhalte ich String1 zurück

 

[berserkerdq2]

Sollte noch erwähnen, bei dem Ergebnis ist es so:

Ich habe 8 Strings die dann jeweils ein Bit erhalten, die das Ergebnis der Multiplikation darstellen, und die 8 Strings werden dann, in einer seperaten Methode, zusammengefügt

(Wobei dass das kleinste Problem hier ist bzw. gar kein Problem ist)

 

[Jw456]

Baue dir doch einen String mit 8 Zeichen.

Baue für eine Methode die zwei 8bitstings addiert. Zuerst addierst du die intern bits da du ein hab Adder hast addierst du den Übertrag zu dem oberen 4 bits. Dann die oberen vier von zweiten oberanten.

Welche möglichkeiten hast du. Um auf einzelne bitz im Strings zuzugreifen?

Dürft ihr String Funktionen benutzen?

 

[berserkerdq2]

Baue dir doch einen String mit 8 Zeichen.

Baue für eine Methode die zwei 8bitstings addiert. Zuerst addierst du die intern bits da du ein hab Adder hast addierst du den Übertrag zu dem oberen 4 bits. Dann die oberen vier von zweiten oberanten.

Welche möglichkeiten hast du. Um auf einzelne bitz im Strings zuzugreifen?

Dürft ihr String Funktionen benutzen?

Leide rnicht, ich darf auch keine neuen Methoden erstellen. (das machts ja für mich so schwer)

Wir dürfen ausschließlich den addierer und die identität nutzen. Keine anderen Methoden oder Funktionen

 

[berserkerdq2]

Ich habe gelesen, dass der Prof auch oft "Spaß" Aufgaben verteilt, die nicht lösbar sind und das soll man herausfinden, ist das vielleicht solch eine? Oder wäre das lösbar?

 

[Staarfightaar]

Ich habe gelesen, dass der Prof auch oft "Spaß" Aufgaben verteilt, die nicht lösbar sind und das soll man herausfinden, ist das vielleicht solch eine? Oder wäre das lösbar?

alles ist in der informatik lösbar, außer die "millionen probleme" wo du ne million kriegst wenn du sie löst wie zb halteproblem

und probleme die nicht in sinnvoller zeit lösbar sind eg handlungsreisenden...diese aufgabe gehört nicht dazu
macht die aufgabe sinn? mir ergibt sich kein sinn... was willst du lernen? wie ma mit strings hantiert ?

 

[Jw456]

Da du keine Schleifen, If , Methoden benutzen darfst, kannst du es nur hinter einander schreiben.
Ich habe die beiden Methoden „add4Bits“ und „get4Bit“ genannt.

das wäre meine Lösungs Variante ist natürlich nicht getestet

String mul4BitTo8Bit(String ob1, String ob2){

        String[] highNibble = {"0000","0"};
        String[] lowNibble = {"0000","0"};
        String  c;
      
        c = get4Bits(ob1,  ob2.charAt(0));
        lowNibble  = add4Bits(lowNibble[0], c );
        highNibble = add4Bits(highNibble[0], lowNibble[1]); // hNibble + carrybit
      
        //schieben
        lowNibble  = add4Bits(lowNibble[0], lowNibble[0]);
        highNibble = add4Bits(highNibble[0], highNibble[0]);
        highNibble = add4Bits(highNibble[0], lowNibble[1]);  // hNibble + carrybit
      
        c = get4Bits(ob1,  ob2.charAt(1));
        lowNibble  = add4Bits(lowNibble[0], c );
        highNibble = add4Bits(highNibble[0], lowNibble[1]); // hNibble + carrybit
      
        //schieben
        lowNibble  = add4Bits(lowNibble[0], lowNibble[0]);
        highNibble = add4Bits(highNibble[0], highNibble[0]);
        highNibble = add4Bits(highNibble[0], lowNibble[1]);  // hNibble + carrybit
      
        c = get4Bits(ob1,  ob2.charAt(2));
        lowNibble  = add4Bits(lowNibble[0], c );
        highNibble = add4Bits(highNibble[0], lowNibble[1]); // hNibble + carrybit
      
         //schieben
        lowNibble  = add4Bits(lowNibble[0], lowNibble[0]);
        highNibble = add4Bits(highNibble[0], highNibble[0]);
        highNibble = add4Bits(highNibble[0], lowNibble[1]);  // hNibble + carrybit
      
        c = get4Bits(ob1,  ob2.charAt(3));
        lowNibble  = add4Bits(lowNibble[0], c );
        highNibble = add4Bits(highNibble[0], lowNibble[1]); // hNibble + carrybit
      
        return highNible[0] + lowNible[0];
    }