Como posso encontrar o número mínimo necessário para adicionar à sequência, de modo que seu xor se torne zero

Dada uma sequência de números naturais, você pode adicionar qualquer número natural a qualquer número na sequência, de modo que seu xor se torne zero. Meu objetivo é minimizar a soma dos números adicionados.

Considere os seguintes exemplos:

1. Para a resposta é ; adicionando a , obtemos .$1, 3$$2$$2$$1$$3 \oplus 3=0$

2. Para a resposta é ; somando a e a , obtemos .$10, 4, 5, 1$$6$$3$$10$$3$$5$$13 \oplus 4 \oplus 8 \oplus 1 = 0$

3. Para a resposta é , pois .$4, 4$$0$$4 \oplus 4 = 0$

Tentei trabalhar em representações binárias do número de sequência, mas ficou muito complexo. Quero saber se existe alguma maneira simples e eficiente de resolver esse problema.

Parece-me que contém todas as informações necessárias: os bits em são os bits que você precisa inserir (exatamente) um dos . Como você só pode adicionar , você precisa encontrar um onde o bit correspondente é e invertê-lo - isso causa o mesmo custo para todos os , ou seja, , portanto a escolha não importa. O problema começa se não houver tal .$a = a_i \oplus \dots \oplus a_n$$1$$a$$a_i$$a_i$$j$$0$$a_i$$2^j$$a_i$

É por isso que você precisa fazer isso iterativamente e trabalhar a partir do menos significativo. Proceda como acima; se não houver um adequado , escolha o com o número máximo de bits restante da posição atual - isso aumenta a chance de encontrar um candidato adequado em futuras iterações -, vire o bit e continue, isso é inverter tudo uns para a esquerda até você virar um zero para um. Observe que ainda adicionamos ). Como carry se propaga apenas para a esquerda, as escolhas anteriores não são invalidadas. Recompute e continue com ; itere até que você tenha .$a_i$$a_i$$1$$2^j$$a$$j+1$$a=0$

Note-se que esta é apenas uma heurística, tanto quanto eu posso dizer: a escolha do pode ser subótimo se faz com que muitos bits em tornar-se não-zero. Não tenho certeza se isso pode ser evitado.$i$$a$

Na verdade, não tenho uma solução, mas aqui estão algumas idéias que surgiram.

Se você observar os resultados do XOR de todos os números na sequência, isso fornecerá um limite superior para o número de adições que você precisa fazer. Por exemplo, no seu exemplo de , temos , portanto, você sabe que não precisa adicionar mais de (porque o 8-bit é o conjunto mais alto). Distribuir até oito "unidades" distribuídas de quatro maneiras é um conjunto bastante pequeno de combinações. Não me lembro dessa fórmula tão tarde da noite, mas há umlá em algum lugar.$10, 4, 5, 1$$10 \oplus 4 \oplus 5 \oplus 1 = 10$$8$$n!$

Para fundamentar um pouco mais essa afirmação, considere números inteiros arbitrários modo que . Os bits acima do bit 3 obviamente cancelam, para que você possa ignorá-los. Para os quatro bits mais baixos, eles são XOR a 8, então o pior caso possível (em termos de número de unidades que você precisa adicionar) é se e (todos os zeros, exceto o bit mais alto), porque você é necessário adicionar +8 a B para definir o bit superior. Se houver qualquer um bits definidos em qualquer um dos números, você precisa adicionar menos.$A,B$$A \oplus B = 8$$A=8$$B=0$

Talvez você possa começar com isso e desenvolver uma quantidade máxima mais apertada para adicionar.