¿Cómo puedo encontrar el número mínimo requerido para agregar a la secuencia de modo que su xor se vuelva cero

8

Dada una secuencia de números naturales, puede agregar cualquier número natural a cualquier número en la secuencia de modo que su xor se convierta en cero. Mi objetivo es minimizar la suma de los números agregados.

Considere los siguientes ejemplos:

  1. por 1,3 la respuesta es 2; agregando2 a 1obtenemos .33=0

  2. Para la respuesta es ; sumando a y a obtenemos .10,4,5,163103513481=0

  3. Para la respuesta es , ya que .4,4044=0

Intenté trabajar en representaciones binarias del número de secuencia, pero se volvió tan complejo. Quiero saber si hay alguna manera simple y eficiente de resolver este problema.

Pravin Gadakh
fuente
2
Una declaración más clara del mismo problema de un póster diferente sobre matemáticas. SE puede encontrar aquí , junto con otra respuesta.
Dilip Sarwate
Interesante problema Parece un problema de suma de subconjuntos en el que el operador de suma se reemplaza por XOR y tal que (si el subconjunto no XOR a 0) el conjunto(s1,s2,,sn) es en sí mismo XORed con otro conjunto {0,1}n(k,k,,k)...
user13675

Respuestas:

5

Me parece que a=aian contiene toda la información necesaria: el 1bits en a son los bits que necesita para voltear (exactamente) uno de los ai. Como solo puedes agregar , tienes que encontrar unoai donde el bit correspondiente j es 0 y voltearlo: esto causa el mismo costo para todos ai, es decir 2j, entonces la elección no importa. El problema comienza si no existeai.

Es por eso que debe hacer esto de forma iterativa y trabajar desde el bit menos significativo hacia arriba. Proceda como arriba; si no hay adecuadoai, elegir la ai con el número máximo de 1bits a la izquierda de la posición actual (esto aumenta la posibilidad de encontrar un candidato adecuado en futuras iteraciones), voltee el bit y continúe, es decir, voltee todos a la izquierda hasta que cambie un cero a uno. Tenga en cuenta que todavía agregamos2j) Como carry se propaga solo a la izquierda, las elecciones anteriores no se invalidan. Recalculara y continuar con j+1; iterar hasta que tengaa=0.

Tenga en cuenta que esto es solo una heurística por lo que puedo decir: la elección de i puede ser subóptimo si causa muchos bits en apara volverse distinto de cero. No estoy seguro de si esto se puede evitar.

Rafael
fuente
0

En realidad no tengo una solución, pero aquí hay algunas ideas que surgieron.

Si observa los resultados de XORing todos los números en la secuencia, eso le da un límite superior en el número de adiciones que necesita hacer. Por ejemplo, en su ejemplo de10,4,5,1, tenemos 10451=10para que sepa que no tiene que agregar más de 8(porque el conjunto de 8 bits es el más alto). Distribuir hasta ocho "unos" distribuidos de cuatro maneras es un conjunto bastante pequeño de combinaciones. No puedo recordar esa fórmula tan tarde en la noche, pero hay unn! ahí en alguna parte.

Para dar a esa afirmación un poco más de fundamento, considere enteros arbitrarios A,B tal que AB=8. Los bits superiores al bit 3 obviamente se cancelan, por lo que puede ignorarlos. Para los cuatro bits inferiores, son XOR a 8, por lo que el peor caso posible (en términos de la cantidad de unidades que necesita agregar) es si A=8 y B=0(todos los ceros excepto el bit más alto) porque necesitará agregar +8 a B para obtener ese conjunto de bits superior. Si hay cualquiera de los bits establecidos en cualquiera de los números, debe agregar menos.

Tal vez pueda comenzar con esto y desarrollar una cantidad máxima más estrecha para agregar.

Mark Bessey
fuente