Multiplikation von zwei 40 Bit Zahlen / C++

die Limits gehören ja bei dem Prinzip zur Aufgabenstellung ;)
 
Ah ok, dann nen "Array of Bits" und weiter wie in nem HW-Multiplizierer.
 
Ich kenne allerdings MSB und LSB als Abkürzung für most significant Bit bzw. least significant Bit. Ich wüsste auch nicht, warum es gerade auf ein Byte ankommen sollte. ;-)
 
anegmawad schrieb:
Ich kenne allerdings MSB und LSB als Abkürzung für most significant Bit bzw. least significant Bit. Ich wüsste auch nicht, warum es gerade auf ein Byte ankommen sollte. ;-)
Zum Vergrößern anklicken....

das stammt noch aus Zeiten da ein Byte als normal galt :)
Immerhin mußte für jede Zahl > 255 dann ein MSB/LSB her und wurde mit Byte als "normaler" Grenze synonym gesetzt!
 
Bei den richtigen E-Freaks geht es natürlich um Bits, aber bei üblicherweise geht es um die Big / Little Endian Frage.
Und zumindest in meinem Anwendungsbereich muss ich da -- normalerweise -- die Bits glücklicherweise nicht selbst drehen, nur die Bytes

Alex
 
Danke für die vielen Anworten! Wir waren wohl auf dem falschen Weg mit der 80 Bit Zahl.

Ich hab ein "abgespecktes" Programm geschrieben, Multiplikation von zwei 3 Bit Zahlen, abspeichern in zwei 3 Bit Zahlen. Doch es funktioniert noch nicht richtig. Das Ergebnis ist komplett in LSB. Hier ist es:

#include <stdio.h>

int main( void)
{
unsigned int zahl1, zahl2, zwischenergebnis, produkt;
unsigned int MSB, LSB;
char zahlarray[3], i;

MSB = 0;
LSB = 0;

printf( "Bitte geben Sie eine Zahl zwischen 0 und 7 ein: ");
scanf( "%d", &zahl1);
printf( "Bitte geben Sie eine zweite Zahl zwischen 0 und 7 ein: ");
scanf( "%d", &zahl2);

produkt = zahl1 * zahl2;

for( i = 0; i < 3; i++)
{
zwischenergebnis = zahl2 / 2;
zahlarray = zahl2 % 2;
}

LSB = zahl1;

for( i = 0; i < 3; i++)
{
if( zahlarray == 1)
{
LSB = LSB + (zahl1 << 1);
}

else
{
LSB = LSB << 1;
}

MSB = MSB << 1;

if( ( ( zahl1 >> 3 & 0x01) && zahlarray) == 1)
{
MSB = MSB | (0x001 << 1);
}
}

printf( "\n\nProdukt: %d", produkt);
printf( "\nLSB, MSB: %d, %d", LSB, MSB);

return 0;
}

irgendwo hab ich wohl einen Fehler gemacht...
 
kannst du deine source mal besser kommentieren? ;)
denkst du auch an den übertrag, wenn du es schon so umständlich mit MSB/LSB machst statt mit einem bit vector/array?
 
ok. ich muss glaub was zum Projekt sagen: Wir simulieren den IAS-Computer. Und der arbeitet mit 40 Bit Zahlen (1 Bit Vorzeichen, 39 Bit Mantisse). Bei der Multiplikation speichert er das LSB in den mq (MultiplierQuotient) und das MSB in den accu.
 
den Übertrag will ich damit auffangen:

MSB = MSB << 1;

if( ( ( zahl1 >> 3 & 0x01) && zahlarray) == 1)
{
MSB = MSB | (0x001 << 1);
}

aber das klappt nicht
 
drummer schrieb:
for( i = 0; i < 3; i++)
{
zwischenergebnis = zahl2 / 2;
zahlarray = zahl2 % 2;
}
Zum Vergrößern anklicken....


was soll da genau geschehen?
soll das zahl2 in bits umwandeln? tut es das auch?
warum lässt du das zwischenergebnis in der schleife setzen, wenn du es immer gleich setzt?

drummer schrieb:
if( ( ( zahl1 >> 3 & 0x01) && zahlarray) == 1)
{
MSB = MSB | (0x001 << 1);
}
Zum Vergrößern anklicken....


warum verwendest du da das i, obwohl das keine schleife ist?
 
das Umspeichern war falsch. Ich habs korrigiert und mit Kommentaren versehen. Richtig rechnen tuts allerdings noch immer nicht.

Code: 
#include <stdio.h>

int main( void)
{
//Variablendeklaration

	unsigned int zahl1, zahl2;		//Faktor 1, Faktor 2 zur Multiplikation
	unsigned int zwischenergebnis;	//zur Umwandlung von zahl2 in ein Bit-Array
	unsigned int produkt;			//Ergebnis zum Überprüfen
	unsigned int MSB, LSB;			//MSB und LSB, beide sollen 3 Bit groß sein
	char zahlarray[3];				//zahl2 soll hier bitweise gespeichert werden
	int i;							//Schleifenzähler
	
	MSB = 0;
	LSB = 0;
	
//Eingabeaufforderung

	printf( "Bitte geben Sie eine Zahl zwischen 0 und 7 ein: ");		//Faktor 1, max 3 Bit groß
	scanf( "%d", &zahl1);
	printf( "Bitte geben Sie eine zweite Zahl zwischen 0 und 7 ein: ");	//Faktor 2, max 3 Bit groß
	scanf( "%d", &zahl2);
	
//Rechnung

	produkt = zahl1 * zahl2;		//Ergebnis zum überprüfen
	
	zwischenergebnis = zahl2 / 2;	//Abspeicherung von zahl2 in Bit-Array
	zahlarray[0] = zahl2 % 2;		//niederwertigstes Bit
	
	for( i = 1; i < 3; i++)	
	{
		zwischenergebnis = zwischenergebnis / 2;
		zahlarray[i] = zwischenergebnis % 2;
	}

	LSB = zahl1;

	for( i = 2; i > 0; i--)								//Binäre Multiplikation
	{
		if( ( ( LSB >> 3 & 0x01) && zahlarray[i]) == 1) //Wenn das höchste Bit von LSB und das nächste Bit von zahl2 eine 1 ist 
		{
			MSB = MSB | (0x001 << 1);					//dann setze das niedrigste Bit von MSB
		}
		
		if( zahlarray[i] == 1)							//Wenn die ite Stelle von zahl2 eine 1 ist
		{
			LSB = LSB + (zahl1 << 1);					//dann shifte zahl1 nach links und addiere die Zahl zu LSB
		}
		
		if( zahlarray[i] == 0)							//Wenn die ite Stelle von zahl2 eine 0 ist 
		{
			LSB = LSB << 1;								//dann shifte LSB um eine Stelle nach links
		}
		
		MSB = MSB << 1;									//Shifte MSB nach links
	}
	
//Ausgabe

	printf( "\n\nProdukt: %d", produkt);		//Ergebnis zum Überprüfen
	printf( "\nLSB, MSB: %d, %d", LSB, MSB);	//LSB, MSB
	
	return 0;
}
 
eigentlich nicht. Ich hole in der for-Schleife das höchste Bit ja zuerst raus (an Stelle 2)
 
Was passiert, wenn du einen ungerade Integer durch 2 teilst?
 
Mh also so richtig verstehe ich das Problem nicht? Ich hab mal fix was
hingeschmiert. Multipliziert zwei 40 bit Zahlen. 'MSB' und 'LSB' steht
dann jeweils in der oberen bzw. unteren Haelfte von 'ergebnis'. Ist
es das was ihr wollt? Das Verfahren ist extremst ineffizient aber vieleicht
halbwegs anschaulich.
BTW: Der Code ist fuer einfache Vorzeichen Darstellung. Fuer
Einer- oder Zweierkomplement muss man die Operanten und das
Ergebnis noch entsprechend umformen!

Code: 
#include <stdio.h>

unsigned long long zahl1 = 0x1234567890LL;
unsigned long long zahl2 = 0x987654321LL;

unsigned char ergebnis[80];
unsigned char operant[80];

void shiftLeft(){
	int i;
	for (i = 79; i >= 0; i--) operant[i] = operant[i - 1];
	operant[0] = 0;
}

void add() {
	unsigned char carry = 0;
	int i;
	for (i = 0; i < 80; i++) {
		switch((operant[i]<<2) + (ergebnis[i]<<1) + carry) {
			case 0: ergebnis[i] = 0; carry = 0; break;
			case 1: ergebnis[i] = 1; carry = 0; break;
			case 2: ergebnis[i] = 1; carry = 0; break;
			case 3: ergebnis[i] = 0; carry = 1; break;
			case 4: ergebnis[i] = 1; carry = 0; break;
			case 5: ergebnis[i] = 0; carry = 1; break;
			case 6: ergebnis[i] = 0; carry = 1; break;
			case 7: ergebnis[i] = 1; carry = 1; break;
			}
		}
}

int main() {
	
	/* Vorzeichen bestimmen */
	unsigned char vz_zahl1 = zahl1 & 0x8000000000LL;
	unsigned char vz_zahl2 = zahl2 & 0x8000000000LL;
	
	/* Vorzeichen 'abschneiden' */
	zahl1 &= 0x7FFFFFFFFFLL;
	zahl2 &= 0x7FFFFFFFFFLL;
	
	int i;
	
	/* Operant laden */
	for (i = 0; i < 40; i++) operant[i] = (zahl1 >> i) & 1;
	
	/* Multiplizieren */
	if((zahl2 & 1) == 1) add();
	
	for (i = 1; i < 39; i++) {
		shiftLeft();
		if(((zahl2 >> i) & 1) == 1) add();
	}
	
	/* Vorzeichen wieder anfuegen */
	ergebnis[79] = vz_zahl1 ^ vz_zahl1;
	
	/* Ergebnis ausgeben */
	printf("MSB: ");
	for (i = 0; i < 40; i++) printf("%d", ergebnis[79 - i]);
	printf("\n");
	printf("LSB: ");
	for (i = 0; i < 40; i++) printf("%d", ergebnis[39 - i]);
	printf("\n");
	
	return 0;
}
 
Zuletzt bearbeitet:
Nö, was "wir" wollten, war dass drummer von sich aus zu nem Ergebnis kommt ;)
 
1. Zum Thema
1.1. Es gibt bereits einen Thread bei heise, in dem ich die Probleme und Lösungen anspreche.

1.2. Die obige Lösung ist etwas aufwändig: Man muss das nicht bitweise machen. Hier kurz die Zusammenfassung des obigen Threads.
Da man einen Übertrag hat, bei Multiplikation in der Größe der Multiplikatoren, nimmt man einfach eine Teilmultiplikation mit einer Wortgröße vor, die halb so groß ist, wie das vom Compiler unterstützte Wort. Haben wir also maximal 64-Bit-Arithmetik, so verwenden wir 32 x 32 in der Teilmultiplikation und erhalten ein 64-Bit-Teilergebnis. Dann eben Geschiebe und kombiniere wie bereits beschrieben. Man kann freilich auch gleich ein Array verwenden und erhält so eine N-Bit-Multiplikation.

2. Zur Bezeichnung
Ich weiß nicht, ob das etwas mit E-Freak zu tun hat. Aber als ich mit 8-Bit-CPUs gearbeitet habe, verwendete man MSB und LSB zur Bezeichnung des Bits. Damals hat man gerne mit 16-Bit-Zahlen herumhantiert. Da sind mir nur die Bezeichnungen High (Hi), Upper bzw. Low (Lo), Lower über den Weg gelaufen. Most und Least wären dann ja schon sprachlich mit dem Superlativ schräg.

Bei größeren Anordnungen, etwa 32-Bit-Zahlen, habe ich nur so etwas wie HiHi, HiLo, LoHi, LoLo gesehen.

Natürlich sind Abkürzungen mehrfach belegt. (Deshalb trägt die das Markenamt auch gar nicht gerne ein.) Aber die häufigste Verwendung ist wohl bezogen auf die Bits:
MSB – Bedeutungsübersicht bei Wikipedia

Der sich anschließende Artikel spricht auch ellenlang von Bits, sagt allerdings am Ende, dass auch der Bezug zu Bytes eine häufige Verwendung sei.

BTW: Geil sind die beiden Bilder im Wiki-Artikel. Ich tendiere ja immer mehr zu Janiers Ansicht …
 
Zuletzt bearbeitet:
Zurück
Oben Unten