Вопрос по xor, algorithm – минимальная сумма, необходимая для приведения xor некоторых целых чисел в ноль

Restatement as a Bounded Integer Linear Programming Problem

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's 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 равным нулю, четное число b [k, i] должно быть 1 для каждого k. Это представлено условиями (B) и (D). (Заметим, что левая сумма в (D) должна быть четной, даже если она равна 2 * s [k] и s [k] является целым числом).

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

Existance of a Solution

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

Given x, y z with x <= y, find a and b such that (x+a) XOR (y+b) = z

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

Упрощенная проблема решена (опять же,ignoring минимальность)

If (y XOR z) >= x then a: = ((y XOR z) - x), b := 0 is a solution (*) If (x XOR z) >= y then a := 0, b := ((x XOR z) - y) is a solution (*) Otherwise, pick an a such that (x+a) XOR z >= y. Such an a always exists, you can for example let a := 2^k with 2^k > max(x,y,z). Setting b := ((x+a) XOR z) - y) yields a solution (*)

(*) Чтобы увидеть, что это действительно решения, вам просто нужно применить немного алгебры. Например, в случае (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 & gt; = 2 решение всегда существует.

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

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

Observations regarding minimality

Возьмите следующую проблему

(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. Это решениеnot хотя минимальный - следующее решение меньше

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 вone из XI 's. Иногда вам нужно добавить его к нескольким XI, чтобы найти минимальное решение.

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

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

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

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

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

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

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

У нас есть два случая:

Случай А. По крайней мере, один 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-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, ... до тех пор, пока по крайней мере два 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 не будут равны нулю.

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

negative ai seem to be necessary: for the case N=1, a1=-x1 is the solution to the problem. I assume therefore that negative ai are allowed also in the general case.

Then, for N=2, there is no solution ("min") at all, apart from the fact the there is a limit to what (negative) numbers can be represented in the computer:

Для 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 & gt; 2: для четного N сделайте попарно "решения". как для N = 2 (с произвольными K 's); для 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, решения могут стать настолько отрицательными, насколько вам угодно.