Binäre Multiplikation von 32 Bit Zahlen -> 64 Bit

Shadow

Mitglied
Hallo!


Ich stehe gerade vor folgendem Problem
Ich will zwei 32 bit unsigned integer zahlen binär miteinander mutliplizieren.
natürlich gibt es hier einen überlauf und man verliert bits.
(Ich verwende lediglich C, kein C++)

um keinen bit zu verlieren müsste ich eine 64 bit variable verwenden.
Durch die Verwendung von "unsigned long long" hab ich aber das problem, dass die ersten 32 bit ident zu den zweiten 32 bit sind
also:
Binäre darstellung
uint32 a = 00010011001100110011001101000000
uint32 b = 00010011001100110011001101000000

bei
unsigned long long iTmpA = a;
bekomme ich wieder
0001001100110011001100110100000000010011001100110011001101000000
wenn ich nun:
iTmpA & 0xFFFFFFFF anwende, bekomme ich leider das selbe ergebnis - also
0001001100110011001100110100000000010011001100110011001101000000

ich hoffe ich hab das problem ausreichend beschrieben.
Wie kann ich dem ganzen habhaft werden?

lg
Shadow
 
Ich stehe gerade vor folgendem Problem
Ich will zwei 32 bit unsigned integer zahlen binär miteinander mutliplizieren.
natürlich gibt es hier einen überlauf und man verliert bits...
Wo bitte soll es bei der Multiplikation einen Überlauf geben?
9 mal 9 ist 81 und kein dreistelliger Wert. Im binären Zahlensystem ist das ebenso.
 
Hallo!

Ich verwende hier eine Festkommadarstellung.

1 bit ist das vorzeichen
3 bit dezimalstelle
28 bit nachomma

(zweierkomplement)

http://de.wikipedia.org/wiki/Festkommazahl
wie man bei diesem beispiel in der wikipedia sieht, hat das ergebnis die doppelte anzahl von komma-stellen
28 -> 56 stellen...


uint32 result;
result = a*b;

a: 00010011001100110011001101000000 entspricht 1.2
b: 00010011001100110011001101000000 entspricht 1.2

result: 11110101110000101001000000000000 -> -0.639999 was offensichtlich falsch ist.

float kann ich nicht verwenden, da das ganze später auf hardware übertragen wird...

ich hoffe ich stehe nicht zu sehr auf der leitung.

lg




Code:
uint32 mult32(uint32* a, uint32* b)
{
	uint32 iResult;
	unsigned long long iResult2;
	
	iResult = (*(uint32*)(a)) * (*(uint32*)(a));
	iResult2 = (*(uint32*)(a)) * (*(uint32*)(a));
		


	for (int i = 31; i >= 0; i--)
	{
		bool res = (iResult) & (1 << i);
		printf( "%d", res );	
	}
	printf( "  :UINT32 Number\n" );


	for (int i = 63; i >= 0; i--)
	{
		bool res = (iResult2) & (1 << i);
		printf( "%d", res );	
	}
	printf( "  :UINT32 Number\n" );


	

	return iResult;
}
 
Zuletzt bearbeitet:
Der Fehler ist in der Berechnungsformel für iResult2. Du multiplizierst zwei 32-Bit-Zahlen, deswegen wird auch nur eine 32-Bit-Multiplikation durchgeführt, deren Ergebnis in eine 64-Bit-Zahl umgewandelt wird, damit es an deine Variable zugewiesen werden kann. Du musst mindestens einen der Operanden zuerst auf unsigned long long casten, damit auch wirklich eine 64-Bit-Multiplikation durchgeführt wird. Dann prüfst du, ob das Ergebnis im darstellbaren Bereich liegt. Wenn das so ist, musst du dann die in der Wikipedia geschilderte Korrektur durchführen, in deinem Fall ein Runden und ein Rechtsshift um 28 Bits. Danach kannst du dann das Ergebnis zurückkonvertieren.
 
Hallo!

Danke für die Antwort.
Ich habe nun mal probeweise die zweite Zahl gecastet
aus:
00010011001100110011001101000000
müsste nun
00000000000000000000000000000000 00010011001100110011001101000000
werden,
aber das resultat ist
10010011001100110011001101000000 10010011001100110011001101000000

es scheint also zusätzlich das erste bit zu kippen...

Code:
uint32 mult32(uint32* a, uint32* b)
{
	uint32 iResult;
	unsigned long long iResult2;
	
	iResult = (*(uint32*)(a)) * (*(uint32*)(b));
	iResult2 = *(unsigned long long*)b;

	for (int i = 31; i >= 0; i--)
	{
		bool res = (*b) & (1 << i);
		printf( "%d", res );	
	}
	printf( "  :UINT32 Number\n" );


	for (int i = 63; i >= 0; i--)
	{
		bool res = (iResult2) & (1 << i);
		printf( "%d", res );	
	}
	printf( "  :UINT32 Number\n" );
	return iResult;
}

habt ihr ne erklärung hierfür ?

lg
 
Probiere mal, was geschieht, wenn du in deiner zweiten Ausgabeschleife die zu shiftende 1 auch auf unsigned long long castest. ;)
 
Code:
iResult2 = *(unsigned long long*)b;

Das kann so nicht funktionieren. Du wandelst einen Zeiger auf eine 4 Byte grosse Zahl in einen Zeiger auf eine 8 Byte grosse Zahl um und dereferenzierst dann. Was du also hinten bekommst ist reiner Zufall.

uint64 iResult2 = (uint64)(*b);
 
Zurück