如何结合位运算符与代数运算符表达32位无符号整数乘法

核心结论 #

不存在和加法恒等式同形式、仅用固定次数的按位与&、按位或|、按位异或^、加减运算、不依赖移位/逐位迭代的闭式表达式，可以等价表示两个任意32位无符号整数的乘法。

加法恒等式的成立逻辑 #

你提到的a + b = a&b + a|b本质是加法进位特性的自然推导：
对二进制每一位来说，两个数同一位都为1时才会产生向高位的进位，值为a_i & b_i（对应权重为2^(i+1)）；不考虑进位的本位值是a_i ^ b_i。我们可以直接推导验证：
a|b = a^b + a&b（两个位只要有一个为1本位就为1，重叠的1位刚好是a&b的部分），代入后可得：
a&b + a|b = a&b + (a^b + a&b) = a^b + 2*(a&b)，这就是标准的加法位运算公式，完全成立。
这个式子成立的核心是：加法的位交互只发生在相邻位的固定1位进位，每一位的贡献可以直接通过位运算取出后线性求和，不需要跨多位的偏移操作。

乘法无法构造同类表达式的原因 #

乘法的位交互是长程、非固定偏移的：两个数相乘时，a的第i位和b的第j位如果都为1，会对结果的第i+j位产生贡献，这个偏移量随i、j的取值从0到62变化，不是加法里固定的1位进位。
如果允许使用移位运算（属于标准位运算范畴），乘法当然可以通过位运算组合实现，这也是所有硬件乘法器的基础逻辑：

uint32_t mul(uint32_t a, uint32_t b) {
    uint32_t res = 0;
    for (int i = 0; i < 32; i++) {
        if (b & (1U << i)) res += a << i;
    }
    return res;
}

但这个实现依赖逐位判断和移位，是迭代形式，不是你期望的、和加法一样用固定个运算符组合就能写出来的简洁闭式ab = f(a,b)。

对你之前推导的说明 #

你写出的推导式cd = (cd)&b + (cd)|b - b只是对加法恒等式做了移项变形，式子左右两边都出现了待求的乘积项cd，属于循环定义，没有实际把乘积拆解为a、b两个输入的位运算组合，没有实际意义。

注：理论上所有整数算术运算都能映射到位运算组合，但乘法不存在和加法那个恒等式结构一致的简洁无迭代表达式。

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