如何在C语言中不使用long long实现拆分存储的64位无符号整数与32位无符号整数相乘

这是个很经典的无符号整数乘法分解问题，刚好可以用纯32位运算来解决，我一步步给你拆解清楚：

问题分析 #

我们的64位无符号数可以表示为 N = a * 2^32 + b（其中a、b是32位无符号整数），要计算它和32位无符号整数c的乘积，结果用e * 2^32 + f表示（e、f也是32位无符号整数）。

先把乘法展开：

N * c = (a * 2^32 + b) * c = a*c*2^32 + b*c

接下来我们把每一部分拆解成32位运算能处理的单元：

步骤1：计算结果的低32位f #

b*c的低32位就是最终结果的低32位f。在C语言中，32位无符号整数相乘时，溢出的部分会自动被截断（取模2^32），所以直接计算即可：

uint32_t f = b * c;

步骤2：计算b*c的高32位 #

要得到b*c的高32位，我们不能直接用64位类型，需要用纯32位运算实现32x32乘法的高32位提取。这里可以把每个32位数拆成高16位和低16位，利用16x16乘法不会溢出32位的特性来计算：

uint32_t mul_high(uint32_t x, uint32_t y) {
    // 将x、y拆分为高16位和低16位
    uint32_t x0 = x & 0xFFFF;
    uint32_t x1 = x >> 16;
    uint32_t y0 = y & 0xFFFF;
    uint32_t y1 = y >> 16;

    // 计算四个16x16的乘积（结果都是32位，不会溢出）
    uint32_t p0 = x0 * y0;
    uint32_t p1 = x0 * y1;
    uint32_t p2 = x1 * y0;
    uint32_t p3 = x1 * y1;

    // 计算中间进位：p0的高16位 + p1的低16位 + p2的低16位，取高16位
    uint32_t carry = ((p0 >> 16) + (p1 & 0xFFFF) + (p2 & 0xFFFF)) >> 16;

    // 最终高32位 = p3 + p1的高16位 + p2的高16位 + 中间进位
    uint32_t high = p3 + (p1 >> 16) + (p2 >> 16) + carry;
    return high;
}

调用这个函数得到b*c的高32位：

uint32_t b_c_high = mul_high(b, c);

步骤3：计算a*c的低32位 #

和f的计算类似，a*c的低32位直接通过32位乘法得到：

uint32_t a_c_low = a * c;

步骤4：计算结果的高32位e #

回到展开式，a*c*2^32的高32位就是a*c的低32位，再加上b*c的高32位，两者的和就是最终结果的高32位e（同样，溢出部分自动取模2^32）：

uint32_t e = a_c_low + b_c_high;

验证例子 #

举个实际例子验证：

• 设a=1，b=0xFFFFFFFF（即64位数2^33 -1），c=2
• 计算f = 0xFFFFFFFF * 2 = 0xFFFFFFFE（正确，低32位是2*(2^32-1)的低32位）
• b_c_high = mul_high(0xFFFFFFFF, 2) = 1（正确，2*(2^32-1)=2^33-2的高32位是1）
• a_c_low =1*2=2
• e=2+1=3（正确，最终结果是2*(2^33-1)=2^34-2，低64位的高32位是3）

最终结果e=3，f=0xFFFFFFFE，完全符合预期。

内容的提问来源于stack exchange，提问作者Khosrow