Найдите наименьшую комбинацию XOR

Рассмотрим следующий код:

#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 XOR .

Но реализация плохая. Оптимизированная версия такова:

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 XOR.
• Количество памяти, необходимое для предварительно вычисленных значений, не имеет значения

Я немного не понимаю, как это записать.