algoritmo relacionados con el XOR

Question

He a $N$ valores $a_1,a_2,a_3\ldots a_N$. Ahora vamos a decir que podría aumentar cualquiera de estos valores por cualquier cantidad tal que la suma XOR se convierte en cero.

$$(a_1+d_1) \oplus (a_2+d_2) \oplus \cdots \oplus (a_n+d_n) =0 $$

necesito encontrar el deltas $d_1,d_2,d_3,\ldots,d_n$ tal que la suma de los deltas se reduce al mínimo. cualquier delta , $d_k \ge 0$.

$N$ a a $100$ en mi caso.

Podría usted por favor decirme si hay alguna forma conocida de cómputo.

Muchas gracias

Answer 1

No tengo una solución óptima, pero aquí al menos un rápido y sucio algoritmo para generar lo que podría ser un "suficientemente buena" solución, al menos para incluso $n$. Pero primero, permítanme reformular el problema un poco:

Dada la no-números negativos $a_1, a_2, \dotsc, a_n$, queremos encontrar los números de $b_1, b_2, \dotsc, b_n$ tal que $a_i \le b_i$ para todos los $i \in \{1, 2, \dotsc, n\}$, $b_1 \oplus b_2 \oplus \dotsb \oplus b_n = 0$ y la suma de $b_1 + b_2 + \dotsb + b_n$ es mínimo. (Podemos, a continuación, deje $d_i = b_i - a_i$ para obtener una solución para el problema original.)

Ahora, aquí es un algoritmo aproximado para obtener tales $b_i$:

1. Empezamos dejando $b_i = a_i$ todos los $i \in \{1, 2, \dotsc, n\}$ y el cálculo de $c = b_1 \oplus b_2 \oplus \dotsb \oplus b_n$.

2. Si $c = 0$, hemos terminado. De lo contrario, deje $k$ ser índice de que el bit superior en $c$, es decir, el mayor entero tal que $2^k \le c$. (Equivalentemente, $k = \lfloor \log_2 c \rfloor$.)

3. Ahora vamos a buscar el incremento más pequeño para algunos $b_i$ que le dará vuelta a la $k$-ésimo bit en ese $b_i$ — y, por tanto, en $c$ — y no más bits. Para hacer eso, vamos a $\beta_i = b_i \bmod 2^k$ y elija $j \in \{1, 2, \dotsc, n\}$ con el fin de maximizar $\beta_j$, sujeto a la condición de que el $k$-ésimo bit de $b_j$ es 0 (es decir, que $b_j \bmod 2^{k+1} < 2^k$). Mientras $n$ es incluso, nos está garantizado para encontrar al menos una de esas $b_j$.

4. A continuación, reemplace $b_j$$b_j + (2^k - \beta_j)$, recalcular $c$ con el nuevo valor de $b_j$, y repita desde el paso 2.

La prueba de que este algoritmo debe terminar, para $n$, se deduce del hecho de que $c$ debe disminuir en cada iteración. Sin embargo, esta prueba sólo funciona incluso para $n$, como por extraño $n$ es posible que el $k$-ésimo bit de $b_i$ es de 1 para todos los $i \in \{1, 2, \dotsc, n\}$ en el paso 3. En ese caso, el incremento de cualquier $b_i$ así como para voltear su $k$-ésimo bit también la vuelta (al menos) el $k+1$-ésimo bit, lo que aumentará $c$.

No es difícil ver que este algoritmo en el hecho de no generar un resultado óptimo $b_1 = b_2 = \max(a_1, a_2)$ para el caso trivial $n = 2$. No sé si es óptimo para cualquier mayor $n$, pero lo dudo. Sin embargo, al menos es bastante rápido y no producir absurdamente grandes soluciones. (De hecho, lo que garantiza que el $d_1 + d_2 + \dotsb + d_n \le a_1 \oplus a_2 \oplus \dotsb \oplus a_n$.)