两个 n 位数 A 和 B 的乘法可以理解为移位的总和：
(A << i1) + (A << i2) + ...
其中 i1, i2, ... 是在 B 中设置为 1 的位数。
现在让我们用 OR 替换 PLUS 以获得我真正需要的新操作：
(A << i1) | (A << i2) | ...
此操作与存在许多更快算法（例如 Schönhage-Strassen）的常规乘法非常相似。我在这里介绍了类似的操作算法吗？
数字的大小为 6000 位。
编辑： 出于某种原因，我没有发布评论的链接/按钮（知道为什么吗？），所以我将编辑我的问题。对于上面定义的操作，我确实搜索了比 O(n^2) 更快的算法。是的，我知道这不是普通的乘法。
有没有类似的算法？我想可能不会。
有什么方法可以加快 O(n^2) 之外的速度吗？可能。如果您认为数字 A 是 A(x) = Σa n x n的类似物，其中 a n是 A 的二进制数字，那么您使用按位 OR 进行的运算（我们称之为 A ⊕ B ）可以表示如下，其中“⇔”表示“模拟”
A ⇔ A(x) = Σa n x n
B ⇔ B(x) = Σb n x n
C = A ⊕ B ⇔ C(x) = f(A(x)B(x)) = f(V(x)) 其中 f(V(x)) = f(Σv n x n ) = Σu(v n )x n其中 u(v n ) = 0 如果 v n = 0，否则 u(v n ) = 1。
基本上，您所做的相当于取两个多项式并将它们相乘，然后识别所有非零项。从位串的角度来看，这意味着将位串视为一个由 0 或 1 组成的样本数组，对这两个数组进行卷积，并折叠非零的结果样本。有一些快速卷积算法是 O(n log n)，例如使用 FFT，这里的“折叠”步骤是 O(n)……但不知何故，我想知道快速卷积的 O(n log n) 评估是否将某些东西（例如大整数的乘法）视为 O(1)，因此您实际上不会获得更快的算法。要么，要么增长顺序的常数太大，以至于您必须拥有数千位才能获得任何速度优势。ORing 就是这么简单。
编辑：似乎有一种叫做“二进制卷积”的东西（例如参见本书）在这里听起来非常相关，但我找不到任何好的链接到它背后的理论以及是否有快速算法。
编辑2：也许这个术语是“逻辑卷积”或“按位卷积”......这是CPAN的一个页面（哎呀！）与沃尔什和哈达玛变换一起谈论它，它们是按位等效于傅立叶变换的。 .. 嗯，不，这似乎是 XOR 而不是 OR 的模拟。
您可以执行此操作 O（A 中的#1 位 * B 中的 #1 位）。
a-bitnums = set(x : ((1<<x) & A) != 0)
b-bitnums = set(x : ((1<<x) & B) != 0)
c-set = 0
for a-bit in a-bitnums:
for b-bit in b-bitnums:
c-set |= 1 << (a-bit + b-bit)
如果 A 和 B 在 1 位的数量上是稀疏的，这可能是值得的。
我能想到的最好的办法是在循环逻辑上使用快速输出。结合使用 themis 描述的非零方法的可能性，您可以通过检查不到 2% 的 N^2 问题来回答您的问题。
下面是一些代码，给出了 80% 到 99% 零之间的数字的时间。当数字在 88% 左右为零时，使用 themis 的方法会变得更好（尽管在下面的示例中没有编码）。
这不是一个高度理论的解决方案，但它是实用的。
好的，这是问题空间的一些“理论”：
基本上，X 的每一位（输出）是由 A 的位沿顶部（MSB 到 LSB 从左到右）和 B 的位沿边（ MSB 到 LSB 从上到下）。由于如果对角线上的任何一个为 1，则 X 的位为 1，因此您可以在单元遍历时执行提前退出。
下面的代码做到了这一点，并表明即使对于大约 87% 为零的数字，您也只需检查大约 2% 的单元格。对于更密集（更多 1）的数字，该百分比下降得更多。
换句话说，我不会担心棘手的算法，只需进行一些有效的逻辑检查。我认为诀窍是将输出的位视为网格的对角线，而不是 A shift-OR 的位与 B 的位。最棘手的是这种情况是跟踪您可以查看的位在 A 和 B 以及如何正确索引位。
希望这是有道理的。如果我需要进一步解释这一点（或者如果您发现这种方法有任何问题），请告诉我。
注意：如果我们更了解您的问题空间，我们可以相应地优化算法。如果您的数字大多非零，那么这种方法比 themis 更好，因为他的结果是需要更多的计算和存储空间（sizeof(int) * NNZ）。
注意 2：这假设数据基本上是位，并且我使用 .NET 的 BitArray 来存储和访问数据。我认为这在翻译成其他语言时不会引起任何重大的麻烦。基本思想仍然适用。
using System;
using System.Collections;
namespace BigIntegerOr
{
class Program
{
private static Random r = new Random();
private static BitArray WeightedToZeroes(int size, double pctZero, out int nnz)
{
nnz = 0;
BitArray ba = new BitArray(size);
for (int i = 0; i < size; i++)
{
ba[i] = (r.NextDouble() < pctZero) ? false : true;
if (ba[i]) nnz++;
}
return ba;
}
static void Main(string[] args)
{
// make sure there are enough bytes to hold the 6000 bits
int size = (6000 + 7) / 8;
int bits = size * 8;
Console.WriteLine("PCT ZERO\tSECONDS\t\tPCT CELLS\tTOTAL CELLS\tNNZ APPROACH");
for (double pctZero = 0.8; pctZero < 1.0; pctZero += 0.01)
{
// fill the "BigInts"
int nnzA, nnzB;
BitArray a = WeightedToZeroes(bits, pctZero, out nnzA);
BitArray b = WeightedToZeroes(bits, pctZero, out nnzB);
// this is the answer "BigInt" that is at most twice the size minus 1
int xSize = bits * 2 - 1;
BitArray x = new BitArray(xSize);
int LSB, MSB;
LSB = MSB = bits - 1;
// stats
long cells = 0;
DateTime start = DateTime.Now;
for (int i = 0; i < xSize; i++)
{
// compare using the diagonals
for (int bit = LSB; bit < MSB; bit++)
{
cells++;
x[i] |= (b[MSB - bit] && a[bit]);
if (x[i]) break;
}
// update the window over the bits
if (LSB == 0)
{
MSB--;
}
else
{
LSB--;
}
//Console.Write(".");
}
// stats
TimeSpan elapsed = DateTime.Now.Subtract(start);
double pctCells = (cells * 100.0) / (bits * bits);
Console.WriteLine(pctZero.ToString("p") + "\t\t" +elapsed.TotalSeconds.ToString("00.000") + "\t\t" +
pctCells.ToString("00.00") + "\t\t" + cells.ToString("00000000") + "\t" + (nnzA * nnzB).ToString("00000000"));
}
Console.ReadLine();
}
}
}
我想，你是在问你
在写“我在这里介绍的操作的类似算法吗？”时给出的加法技术的名称......
你看过农民乘法技术吗？
如果您在此示例中没有获得第 3 列，请阅读 Wikipedia 描述。
B X A
27 X 15 : 1
13 30 : 1
6 60 : 0
3 120 : 1
1 240 : 1
B is 27 == binary form 11011b
27x15 = 15 + 30 + 120 + 240
= 15<<0 + 15<<1 + 15<<3 + 15<<4
= 405
听起来很熟悉？
这是你的算法。
lsb是，则将A添加到 C1更新如果您正在尝试获得一种用于 6000 位的移位和 OR 运算的快速算法，
实际上可能有一个。我会考虑更多。
看起来像是“模糊”了一个数字。有趣的。
这里是一个相当粗略的例子，
110000011 X 1010101 would look like
110000011
110000011
110000011
110000011
---------------
111111111111111
两个数字中的1s 的数量将决定对所有位都设置的数字的模糊量。
想知道你想用它做什么...
Update2这是两个 6000 位数字的 shift+OR 运算的本质。
我还没有为此找到一个干净的算法。已经为其他想要重新检查或从这里走得更远的人进行了更新。此外，描述这种操作的必要性可能会激发更多的兴趣:-)
只需使用任何 FFT 多项式乘法算法并将所有大于或等于 1 的结果系数转换为 1。
例子：
10011 * 10001
[1 x^4 + 0 x^3 + 0 x^2 + 1 x^1 + 1 x^0] * [1 x^4 + 0 x^3 + 0 x^2 + 0 x^1 + 1 x^0]
== [1 x^8 + 0 x^7 + 0 x^6 + 1 x^5 + 2 x^4 + 0 x^3 + 0 x^2 + 1 x^1 + 1 x^0]
-> [1 x^8 + 0 x^7 + 0 x^6 + 1 x^5 + 1 x^4 + 0 x^3 + 0 x^2 + 1 x^1 + 1 x^0]
-> 100110011
有关算法的示例，请检查：
http://www.cs.pitt.edu/~kirk/cs1501/animations/FFT.html
顺便说一句，它具有线性复杂度，即 O(n log(n))
另见：
http://everything2.com/title/Multiplication%2520using%2520the%2520Fast%2520Fourier%2520Transform