Минимальная сумма, необходимая для того, чтобы сделать xor некоторых целых чисел равными нулю

Ответ 1

Пересчет как ограниченная проблема с линейным программированием

Задача может быть переформулирована как следующая ограниченная задача ILP (целочисленное линейное программирование).

Let x1,...,xN be as in the original problem, i.e. the goal is to minimize(a1+...+aN)
under the conditions (x1+a1) XOR ... (xN+aN) = 0, a1,...,aN >= 0.

The following is than an equivalent bounded ILP:
Find b[k,i] (0 <= k <= K, 1 <= i <= N) and s[k] (0 <= k <= K) such that
  (A) b[k,i] in {0, 1} for all i=1..n, k=0..K,
  (B) s[k] is an integer >= 0 for all k=0..K,
  (C) sum(b[k,i]*2^k, k=0..K) >= x[i] for all i = 1..N,
  (D) sum(b[k,i], i=1..N) = 2*s[k] for all k = 0..K
and minimize
  sum(b[k,i]*2^k, i=1..n, k=0..K).

From a solution of the bounded ILP the ai are obtained by
  a[i] = sum(b[k,i]*2^k, k=0..(K-1)) - x[i]

b [k, i] является просто k-м битом двоичного представления (xi + ai) здесь (условия (A) и (C)). Чтобы сделать общий XOR zero, четное число b [k, i] должно быть равным 1 для каждого k. Это представлено условиями (B) и (D). (Заметим, что левая сумма в (D) должна быть четной, если она равна 2 * s [k], а s [k] - целое число).

K, то есть количество бит (плюс одно, фактически), необходимое для представления всех (xi + ai), должно быть определено заранее. Выбирая K такой, что все xi являются < 2 ^ K должно быть достаточно, то есть ai на один бит больше самого большого xi. Но выбор большего K не имеет значения, верхние биты просто выйдут как ноль. Если K выбран до малого, ILP не будет иметь решения.

Существование решения

Игнорируя условие минимальности, проблему можно пересчитать как

Учитывая x, y z с x <= y, найдем a и b такие, что (x + a) XOR (y + b) = z

Учитывая экземпляр исходной задачи, с N >= 2. Пусть x = x1, y = x2, z = (x3 XOR x4 XOR... xn). Если вы найдете подходящие a и b, установите a1 = a, a2 = b, a3 =... = an = 0, чтобы получить решение исходной задачи.

Упрощенная задача решается (опять же, игнорируя минимальность) на

• Если (y XOR z) >= x, то a: = ((y XOR z) - x), b: = 0 - решение (*)
• Если (x XOR z) >= y, то a: = 0, b: = ((x XOR z) - y) является решением (*)
• В противном случае выберите a такое, что (x + a) XOR z >= y. Такое a всегда существует, вы можете, например, дать a: = 2 ^ k с 2 ^ k > max (x, y, z). Установка b: = ((x + a) XOR z) - y) дает решение (*)

(*) Чтобы убедиться, что это действительно решения, вам просто нужно применить немного алгебры. Например, в случае (1) после подстановки a и b вы получаете: (x + (y XOR z) -x) XOR (y + 0). Что идентично: (y XOR z) XOR y и, следовательно, к: z. что и требовалось доказать Случай (2) работает аналогичным образом. В случае (3) вы получаете: (x + a) XOR (y + ((x + a) XOR z) -y) = (x + a) XOR ((x + a) XOR z) = z.

Это показывает, что при N >= 2 решение всегда существует.

Независимо от того, минимальны ли эти решения, я не знаю. В случае (3) это, очевидно, зависит от выбора a, поэтому, по крайней мере, вам нужно будет найти оптимальный выбор для a. Возможно также, что исходная проблема позволяет решать меньшие решения, чем упрощенная задача. Anway, может быть, это повторение поможет кому-то разобраться в полном решении.

Кстати, тот факт, что исходные проблемы по существу оставляют вам полную свободу того, как "распространять" значения коррекции ai по xi, заставляет меня задаться вопросом, не является ли это эквивалентом какой-либо проблемы с рюкзаком. Если это так, поиск минимального решения вполне может быть NP-трудным.

Наблюдения относительно минимальности

Возьмем следующую задачу:

(1+a1) XOR (3+a2) XOR (6+a3) = 0

В двоичном формате это

(001b+a1) XOR (011b+a2) XOR (110b+a3) = 0

Остаток для a1 = a2 = a3 = 0 равен 001b XOR 011b XOR 110b = 100b. Очевидным решением является, таким образом, a1 = 4, a2 = 0, a3 = 0. Или, альтернативно, a1 = 0, a2 = 4, a3 = 0. Это решение не является минимальным, хотя следующее решение меньше

a1=1, a2=1, a3=0

Он также минимален, так как все меньшие решения могут иметь только один ненулевой ai, а все члены (2 XOR 3 XOR 6), (1 XOR 4 XOR 6), (1 XOR 3 XOR 7) -нуль.

Это показывает, что алгоритм gree, который работает снизу (т.е. младший бит) вверх, может работать, поскольку такой алгоритм будет пропускать первые два бита, так как их остаток равен нулю изначально.

Это также показывает, что вы не можете выбрать определенный ненулевой бит k из остатка и попытаться его обнулить, добавив 2 ^ k к одному из xi. Иногда вам нужно добавить его к нескольким xi, чтобы найти минимальное решение.

Это подталкивает меня немного дальше к вере в то, что найти минимальное решение - довольно сложная проблема.

Ответ 2

Ссылаясь на мой комментарий - вопрос еще не ответил:

• отрицательный ai представляется необходимым: для случая N = 1 a1 = -x1 является решением проблемы. Поэтому я предполагаю, что отрицательный ai допускается также в общем случае.

• Тогда для N = 2 решения ( "min" ) вообще не существует, кроме того, что существует предел тому, что (отрицательные) числа могут быть представлены в компьютере:

При N = 2 множество: a1 = x2 + K и a2 = x1 + K. Это дает:

(x1 + x2 + K) XOR (x2 + x1 + K) = 0, независимо от K

Сумма (a1 + a2) = (x1 + x2 + 2 * K)

Нет минимального решения: мы можем сделать K еще более отрицательным.

Аналогично для N > 2: для N четно создавайте парные "решения", как для N = 2 (с произвольными K); для N нечетных, один один из них обрабатывает его как для N = 1 - и остальные N-1 обрабатываются так же, как и для N.

Во всех случаях вы создаете ZERO XOR ZERO XOR ZERO... = ZERO, где ZERO всегда является парой типа (am = xm + 1 + K; am + 1 = xm + K), за исключением случаев, когда N нечетно, где у вас есть еще один фактор, т.е. типа {am = -xm), За исключением N = 1, решения могут стать столь же большими, как вам нравится.

Ответ 3

Возможно, первый набег на минимум - N > 1, все a (i) положительные - по следующим строкам. Позвольте мне сначала указать некоторую терминологию.

Инициализировать y (i) = x (i); y (i) означает (x (i) + a (i)), поэтому мы фактически инициализируем a (i) = 0 (для я = 1..N). Аналогично, определим Q = y (1) ^ y (2) ^... ^ y (N) (^ обозначает XOR); первоначально Q = P.

Мы скорректируем y (i), чтобы сделать Q zero, всегда сохраняя y (i) >= x (i) - i.e.: a (i) >= 0.

Рассмотрим для каждого числа (x, y, a, P, Q) его двоичное (бит-) разложение, число битов на m = 0,1,2,...: бит m представляет значение 2 ** m -части в числе.

Обратите внимание, что бит не равен нулю в Q тогда и только тогда, когда число y (i), которое имеет один и тот же бит, отличное от нуля, является нечетным.

Выполните следующие действия. Сканирование битов-нарушителей (значение 1) в Q, сверху вниз, т.е. Начиная с самого высокого ( "оставшегося" ) бита, равного 1. Пусть это бит #m.

Имеем два случая:

Случай A. Существует по крайней мере один y (i), который имеет нуль в бит m. Определим C как совокупность всех таких y (i).

Мы собираемся выбрать один из них (см. ниже) и установить его m-бит в 1, т.е. сменив

 y(i) = y(i)+(2**m). For the moment, just define INCREMENT=(2**m).

Чтобы определить наш выбор y (i) в коллекции C, мы попытаемся частично компенсировать ИНКРИМЕНТ (2 ** m) с помощью ОБРАЩЕНИЯ как можно больше:

Итерации по битам m-1, m-2,... до тех пор, пока у нас не будет бит #n, где (1.) Q имеет 1 (то есть: другой бит-бит, который мы хотим удалить), и (2.) по крайней мере один из y (i) в C также имеет 1.

Если это удастся, тогда (1.) установите:

INCREMENT = INCREMENT - 2**n (note that this remains positive);

(2.) уменьшить коллекцию C, чтобы сохранить только те y (i), у которых бит #n отличен от нуля; и (3.) повторите процесс, еще раз сканируя бит.

Как только мы не сможем продолжить дальше, произвольно выберите один из оставшихся y (i) из C и увеличьте его с помощью INCREMENT. Обновить Q. Это удаляет биты {m, n,...} из Q, добавляя

 (2**m - 2**n - ...)

к выбранному y (i), устанавливает свой бит #m в 1 (это было 0), а его биты n,... - 0 (это были 1).

Случай B. Ни один из y (i) не имеет нуля в бит #m. В этом случае:

Итерацию над битами k = m + 1, m + 2,... пока, по крайней мере, TWO y (i) не будет иметь нулевой бит в этом бите. Определите C1 как совокупность всех таких y (i) и сделайте копию коллекции C2. Также определите

INCREMENT1 as (2**k - 2**m) and set INCREMENT2 = 2**k.

Процесс {C1, INCREMENT1}, как это было в случае A.

Удалить окончательный выбор y (i) из коллекции C2. Затем обрабатываем {C2, INCREMENT2} аналогично.

Повторите все это, пока все биты в Q не будут нулевыми.

Я не пытался доказать, что эта процедура дает истинный минимум, но я верю, что этот подход может стать хорошей отправной точкой для размышления о (такой структуре) такого доказательства.