拆分整数乘法
我需要一个使用两个32位整数作为参数的算法，并将这些参数的乘法分成两个其他32位整数：32位最高位部分和32位最低位部分。
我会尝试：
uint32_t p1, p2; // globals to hold the result void mult(uint32_t x, uint32_t y){ uint64_t r = (x * y); p1 = r >> 32; p2 = r & 0xFFFFFFFF; } 尽管它工作1 ，但它不能保证机器中存在64位整数，编译器也不能使用它们。
那么，解决它的最佳方法是什么？
注1 ：实际上，它不起作用，因为我的编译器不支持64位整数。
Obs ：请避免使用boost 。
只需使用16位数字。
void multiply(uint32_t a, uint32_t b, uint32_t* h, uint32_t* l) { uint32_t const base = 0x10000; uint32_t al = a%base, ah = a/base, bl = b%base, bh = b/base; *l = al*bl; *h = ah*bh; uint32_t rlh = *l/base + al*bh; *h += rlh/base; rlh = rlh%base + ah*bl; *h += rlh/base; *l = (rlh%base)*base + *l%base; }
正如我评论的那样，您可以将每个数字视为长度为32的二进制字符串。
只需使用学校算术将这些数字相乘即可。 您将获得一个64个字符长的字符串。
然后分区吧。
如果你想快速乘法，那么你可以看看Karatsuba乘法算法。
这是Karatsubas算法的解释和实现。 我已经下载了代码并运行了几次。 看起来它做得很好。 您可以根据需要修改代码。
如果支持unsigned long类型，则应该有效：
void umult32(uint32 a, uint32 b, uint32* c, uint32* d) { unsigned long long x = ((unsigned long long)a)* ((unsigned long long)b); //Thanks to @Толя *c = x&0xffffffff; *d = (x >> 32) & 0xffffffff; }
逻辑借鉴于此 。