在Bringmann16文章中提出的算法中，建议使用布尔卷积来获得两组正整数的sumset。
在上面的工作中，两组都表示为位掩码 - indicator vectors。如果将它们表示为1 + bit(0) * x + bit(1) * x^2 + ... + bit(i) * x^(i + 1) + ... + bit(n - 1) * x^n形式的多项式，那么它们的产品实际上只包含那些单项式，其幂可以是第一组，也可以是第二组或者是总和。对于子集和问题，乘积系数无关紧要。它们的值只表明有多少种方法可以得到数字（相应单项式的程度）作为第一组和第二组元素之和或者可以为0.任何系数的值都受到两组（s）更大尺寸的限制。
为了将多项式乘法问题转换为大整数（指标向量）乘法问题，需要在指标向量的每个位之后附加log(s)零比特。如果位(log(s) + 1) * i ... (log(s) + 1) * (i + 1) - 1在产品位集中并非全部清零，则可以实现相应的sum = i。
对于大型int乘法算法（Karatsuba-like或基于FFT），它为问题大小提供了额外的对数因子。我想消除对数填充。
我认为如果我使用简单的教科书ijk算法来乘以两个整数是可行的。我只需要使用逻辑OR而不是ADD进行求和。但是该算法具有二次运行时复杂性。
在基于FFT的算法（如Schönhage–Strassen algorithm）的情况下，是否可以用ORing替换求和？
很不幸的是，不行。基于FFT或NTT的乘法基于卷积定理（https://en.wikipedia.org/wiki/Convolution_theorem）
卷积定理仅起作用，因为FFT / NTT将长度为N的输入向量表示为N个线性无关指数序列的总和。
要使N个不同的线性独立指数序列，您需要至少N个不同的元素作为基础，这意味着元素的大小必须至少为log N位。
用于+和*的元素类型和操作也必须形成一个环（https://en.wikipedia.org/wiki/Ring_(mathematics)），OR不满足。