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

12

Здесь вопрос, который касается алгоритма и битовой операции xor. Нам даютx1*x2*x3*....*xn=Pгде звезда (*) представляет операцию XOR (побитовую) иx1 to xn are positive integers, P также является положительным целым числом. Мы должныfind min(a1+a2+a3+.....an) such that это соотношение имеет место - & gt;(x1+a1)*(x2+a2)*(x3+a3)*....*(xn+an)=0, & APOS; + & APOS; представляет нормальную операцию сложения.

Я думаю, что нужно больше деталей. Каковы ограничения наai? Должны ли они быть позитивными? Насколько большими они могут быть? IVlad
@IVlad Все целые числа положительные. halkujabra
@ user1708762 Вам удалось решить проблему в условиях минимальности? mayank
Являютсяxi положительные целые числа или они тоже могут быть отрицательными? IVlad
@IVlad Все целые числа неотрицательны! Таким образом, также все значения & gt; = 0 halkujabra

Ваш Ответ

3   ответа
4
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, чтобы найти минимальное решение.

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

Все целые числа неотрицательны! Таким образом, также все значения & gt; = 0 halkujabra
@ user1708762 Да, я понял это. Мой ответ дает только ai 's = 0. В противном случае, тривиально видеть, что решение всегда существует, просто установите ai = -xi.
1

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 не будут равны нулю.

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

1

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, решения могут стать настолько отрицательными, насколько вам угодно.

Для четного N, налагая требование положительного ai, вы получаете меньший минимум, чем ваш общий {a (i) = sum (all x (j)) - x (i)}, путем спаривания вдоль линий в моем ответе. Первый выстрел должен был бы отсортировать x (i), затем попарно установить {a (i) = (x (j) - (x (i)); a (j) = 0}. Результатом является сумма парные различия (x (j) - (x (i)). Кстати, я полагаю, что мы также должны ждать ответа от человека, который задал вопрос, чтобы уточнить, что требуется / разрешено.
В некотором смысле, да, вы, конечно, правы (и это также относится к нечетным N 2, настраивая K ', чтобы подтолкнуть отрицательную сумму к пределу, который представлен), но я предполагаю, что это не тот тип решения, которое искал аскер ...
Хм, так что даже для N, естьis решение
Хм, так что даже для N, решениеalways существует, даже если a [i] должны быть положительными. Таким образом, возникает вопрос (только для четного N!), Является ли a [i] = x [1] + ... + x [i-1] + x [i] + ... + x [n] минимальным решением , Для N = 1 я согласен, что не существует решения с a1 & gt; = 0, если только вы не допустите переполнение. Однако я не убежден, что то же самое верно для N & gt; 1, N нечетно. Кто сказал, что вы не можете найтиodd число целых чисел yi с yi & gt; = xi и y1 * ... * yn = 0?
Я только что понял, что a [i] = x [1] + ... + x [i-1] + x [i] + ... + x [n] определенноnot минимальное решение для нечетных N. Создание двух смежныхpairs из (x [i] + a [i]) отменяют друг друга, то есть a [i] = {x [i-1], если i нечетное, x [i + 1], если i четное}, как правило, приводит к меньшее решение. Таким образом, для четного N x0 + ... + xn является границей для a0 + ... + an.

Похожие вопросы