iとjごとに[i＆j] + = b [i] * c [j]を効率的に実行するにはどうすればよいですか？

Question

私は私が私が探しているすべての0 < = I、J < = 1024用a[i&j] += b[i] * c[j]を持っていることを新しい配列aが効率的な検索したい1024未満のサイズを持つ2つの整数配列bとcを持っています正規の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

ノー怖いです。可能なすべての組み合わせとiとjの場合は、にb[i]とc[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]; 
}