Multiplying two 32-bit numbers without using a 64-bit int
We are performing 32 bit 32 bit multiplication using the following algorithm
Let's want to multiply (32 bits) by b (32 bits), both signed and
a = ah * 2 ^ 16 + al [ah - Higher 16 bits, al - lower 16 bits]
b = bh * 2 ^ 16 + bl [bh - higher 16 bits, bl - lower 16 bits]
We effectively do
Result = (al * bl) + (((ah * bl) + (al * bh)) * 2 ^ 16) + ((ah * bh) * 2 ^ 32) ~~~
My question is,
Do they have a better way to do this?
source to share
In any mainstream compiler, emulating 64-bit ints on a 32-bit platform will be about as efficient as the step-by-step mathematics itself. But it will be much more reliably correct.
When doing simple arithmetic with values large enough to overflow, even the most highly customizable math library I've seen just uses int64.
source to share
Answer: no, there is no better way to do things other than using bit offsets and masks instead of 2 ^ n. Namely:
a * 2^n <=> a << n
Second, are your ints or unsigned signed? If they are signed, it will change the situation.
Third, I'm not sure if your 2 ^ 15 is right. If it is at least unsigned, you want to shift the bit by 16, not 15.
Finally, you need to watch out for integer overflow in the lowest int. If you are summing numbers in bottom order int that overflow its capacity, you need to increase the height of the int correctly.
source to share
You need to know (specify) how a 64-bit value should be stored - presumably it's a pair of 32-bit values, perhaps two array elements or two structure elements. You also need to think about how the information about the mark will be saved in the result.
Mechanically, you would probably want to convert both signed values to unsigned, and then split and reassemble across the lines you specify, while doing so to make sure the transfer from the 32-bit low-order value is handled properly in 32-bit high order. bit value.
Depending on your initial design decisions, you may also need to enter a feature representation of the result, and possibly even all the other bits.
Similar comments refer to multiplying two 16-bit numbers with no 32-bit results, which was once important, but most people don't need to worry.
source to share