找到XOR的最低组合

Question

请考虑以下代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main (int argc, char *argv[])
{
  time_t seed;
  time (&seed);

  srand (seed);

  int i, j, k, l;

  // init random values s1 .. s8

  int s[8];
  for (l = 0; l < 8; l++) s[l] = rand ();

  // zero result

  int r[16];
  for (j = 0; j < 16; j++) r[j] = 0;

  // do 100 random xor functions

  for (i = 0; i < 100; i++)
  {
    // generates random function to show why CSE must be computed in runtime
    int steps[16];
    for (j = 0; j < 16; j++) steps[j] = rand ();

    // _here_ is optimization possible
    // run function MANY times to show that optimization makes sense

    for (l = 0; l < 1000000; l++)
    {
      for (j = 0; j < 16; j++)
      {
        int tmp = 0;
        for (k = 0; k < 8; k++) tmp ^= ((steps[j] >> k) & 1) ? s[k] : 0;

        r[j] += tmp;
      }
    }

    for (j = 0; j < 16; j++) printf ("%08x\n", r[j]);

    puts ("");
  }

  return 0;
}

在代码中,以下展开的函数在循环中执行多次:

r[ 0] += s01 ^ s03;
r[ 1] += s02 ^ s04;
r[ 2] += s03 ^ s05;
r[ 3] += s02;
r[ 4] += s03;
r[ 5] += s04 ^ s06;
r[ 6] += s03;
r[ 7] += s04;
r[ 8] += s02 ^ s04 ^ s05 ^ s07;
r[ 9] += s03 ^ s04 ^ s05 ^ s07;
r[10] += s04 ^ s05 ^ s06;
r[11] += s05 ^ s06 ^ s08;
r[12] += s03 ^ s06;
r[13] += s06;
r[14] += s02 ^ s03 ^ s04 ^ s05 ^ s06 ^ s07;
r[15] += s03 ^ s04 ^ s05 ^ s06;

共计23次异或.

但实施很糟糕.优化版本是这样的:

int s04___s05 = s04 ^ s05;
int s03___s06 = s03 ^ s06;
int s04___s05___s07 = s04___s05 ^ s07;
int s03___s04___s05___s06 = s03___s06 ^ s04___s05;

r[ 0] += s01 ^ s03;
r[ 1] += s02 ^ s04;
r[ 2] += s03 ^ s05;
r[ 3] += s02;
r[ 4] += s03;
r[ 5] += s04 ^ s06;
r[ 6] += s03;
r[ 7] += s04;
r[ 8] += s02 ^ s04___s05___s07;
r[ 9] += s03 ^ s04___s05___s07;
r[10] += s04___s05 ^ s06;
r[11] += s05 ^ s06 ^ s08;
r[12] += s03___s06;
r[13] += s06;
r[14] += s02 ^ s03___s04___s05___s06 ^ s07;
r[15] += s03___s04___s05___s06;

总共15次XOR.

我正在寻找一种自动执行此步骤的算法,并找到使用最低XOR数的解决方案.

如果有多个解决方案,请找到具有最低存储数量的解决方案进行预计算.

如果还有多个解决方案,那么选择哪个并不重要.

一些额外的信息:

• 在实际程序中,函数的XOR可以是随机的,因为它们依赖于用户输入.
• 总共完成了16个步骤.
• 每步的XOR数可以在0到7之间.
• 预计算值所需的存储数量无关紧要

我对如何写这个有点迷茫.

Answer 1

我们想要计算r[i]. 它等于最多 8 个输入之间进行异或运算。
现在，考虑一下： s8 ^ s6 ^ s5 ^ s4 ^ s3 ^ s2 ^ s1，就像数字 10111111。
如果我们s在异或运算中使用相应的值，则为 1，如果不使用对应值，则为 0。
我们可以预先计算所有可能的 2^8 变化：

t[0] = 0       (00000000, nothing)
t[1] = s1      (00000001)
t[2] = s2      (00000010)
t[3] = s2 ^ s1 (00000011)
t[4] = s3      (00000100)
t[5] = s3 ^ s1 (00000101)
...
t[255] = s8 ^ s7 ^ s6 ^ s5 ^ s4 ^ s3 ^ s2 ^ s1 (11111111)

然后在循环中，如果您想要计算：

r[0] = s1 ^ s3

s1 ^ s3 在我们的表示中是 00000101 = 5，这为我们提供了预先计算的查找表的索引：

r[0] = t[5]

这可以解决您的问题，而无需循环中的任何异或。