如何有效地为每个i和j执行[i＆j] + = b [i] * c [j]？

Question

我有两个整数数组b和c，大小小于1024.我想有效地找到一个新的数组a，这样我每隔0 <= i，j <= 1024就有a[i&j] += b[i] * c[j]。我正在寻找其他解决方案比常规的O（n ^ 2）。

基本上我希望改进这个：

for(int i = 0; i < 1024; ++i){
   for(int j = 0; j < 1024; ++j){
      a[i&j] += b[i] * c[j];
   }
}

Answer 1

我不敢。由于你想为b[i]和c[j]的每种可能组合添加i和j，你必须遍历所有这些组合。但是，你可以改进。

如果你只想要一个特定的a[n]，而不是整个数组a，那么有更好的方法。

int n = 666; // Input
// Split input into bits
int e[10] = {};
for (int i = 0, ne = 0; i < 10; i++) {
    if ((n & (1<<i)) == 0)
        e[ne++] = i; // Store the indices of zero bits of input
}

现在从输入创建b[i]和c[j]：

int i, j;
// Enumerate all possible combinations of i and j
for (int count = 0; count < pow(3, ne); count++){
    int t = count;
    i = j = 0;
    for (int k = 0; k < ne; k++) {
        switch (t % 3) {
            case 0: break;
            case 1:
                i |= 1 << k;
                break;
            case 2:
                j |= 1 << k;
                break;
        }
        t /= 3;
    }
    i |= n, j |= n;
    a[n] += b[i] * c[j];
}