Wie kann ich die Mindestanzahl finden, die zum Hinzufügen zur Sequenz erforderlich ist, sodass ihr xor Null wird?

8

Bei einer gegebenen Folge natürlicher Zahlen können Sie jeder Zahl in der Folge eine beliebige natürliche Zahl hinzufügen, sodass ihr xor Null wird. Mein Ziel ist es, die Summe der hinzugefügten Zahlen zu minimieren.

Betrachten Sie die folgenden Beispiele:

  1. Für die Antwort ; Wenn wir zu 1 addieren , erhalten wir 3 \ oplus 3 = 0 .2 2 1 3 3 = 01,322133=0

  2. Für 10,4,5,1 die Antwort 6 ; Addiert man 3 zu 10 und 3 zu 5 so erhält man 13481=0 .

  3. Für 4,4 die Antwort 0 , da 44=0 .

Ich habe versucht, an binären Darstellungen der Sequenznummer zu arbeiten, aber es wurde so komplex. Ich möchte wissen, ob es einen einfachen und effizienten Weg gibt, um dieses Problem zu lösen.

Pravin Gadakh
quelle
2
Eine klarere Darstellung des gleichen Problems aus einem anderen Poster zu math.SE finden Sie hier zusammen mit einer anderen Antwort.
Dilip Sarwate
Interessantes Problem. Es sieht aus wie ein Teilmengen- Summenproblem, bei dem der Summenoperator durch XOR ersetzt wird und die Menge selbst mit einer anderen Menge XOR- verknüpft wird (wenn die Teilmenge nicht XOR auf 0 setzt) ...{ 0 , 1 } n( k , k , , k )(s1,s2,,sn){0,1}n(k,k,,k)
user13675

Antworten:

5

Es scheint mir, dass alle notwendigen Informationen enthält: Die Bits in sind die Bits, die Sie benötigen, um (genau) eines der . Wie Sie nur zu dürfen hinzufügen , müssen Sie einen finden wo das entsprechende Bit ist und es drehen - dies die gleichen Kosten für alle Ursachen , das ist , so dass die Wahl nicht Sache tut. Probleme beginnen, wenn es kein solches . 1 a a i a i j 0 a i 2 j a ia=aian1aaiaij0ai2jai

Deshalb müssen Sie dies iterativ tun und vom niedrigstwertigen Bit aufwärts arbeiten. Gehen Sie wie oben vor; Wenn es kein geeignetes , wählen Sie das mit der maximalen Anzahl von Bits, die von der aktuellen Position übrig sind - dies erhöht die Chance, in zukünftigen Iterationen einen geeigneten Kandidaten zu finden -, drehen Sie das Bit um und übertragen Sie, dh alle umdrehen Einsen nach links, bis Sie eine Null in eine Eins umdrehen. Beachten Sie, dass wir noch ) hinzufügen . Da sich der Übertrag nur nach links ausbreitet, werden frühere Auswahlmöglichkeiten nicht ungültig. Berechne und fahre mit ; iterieren Sie, bis Sie .aiai12jaj+1a=0

Beachten Sie, dass dies nur eine Heuristik ist, soweit ich das beurteilen kann: Die Wahl von kann suboptimal sein, wenn dadurch viele Bits in ungleich Null werden. Ich bin mir nicht sicher, ob dies vermieden werden kann.ia

Raphael
quelle
0

Ich habe eigentlich keine Lösung, aber hier sind ein paar Ideen, die aufgetaucht sind.

Wenn Sie sich die Ergebnisse der XOR-Verknüpfung aller Zahlen in der Sequenz ansehen, ergibt sich eine Obergrenze für die Anzahl der hinzuzufügenden Ergänzungen. In Ihrem Beispiel für haben wir beispielsweise , sodass Sie wissen, dass Sie nicht mehr als hinzufügen müssen (weil das 8-Bit ist der höchste Satz). Das Verteilen von bis zu acht "Einsen", die auf vier Arten verteilt sind, ist eine relativ kleine Menge von Kombinationen. Ich kann mich so spät in der Nacht nicht an diese Formel erinnern, aber es gibt einirgendwo da drin.10,4,5,110451=108n!

Um diese Aussage ein wenig fundierter zu machen, betrachten Sie beliebige ganze Zahlen so dass . Die Bits höher als Bit 3 heben sich offensichtlich alle auf, sodass Sie sie ignorieren können. Für die unteren vier Bits sind sie XOR bis 8, daher ist der schlechteste Fall (in Bezug auf die Anzahl der Einsen, die Sie hinzufügen müssen), wenn und (alle Nullen mit Ausnahme des höchsten Bits), weil Sie Sie müssen +8 zu B hinzufügen, um das oberste Bit zu erhalten. Wenn es irgendwelche eines Bits in entweder der Zahlen festlegen, müssen Sie weniger hinzuzufügen.A,BAB=8A=8B=0

Vielleicht können Sie davon ausgehen und eine engere maximale Menge entwickeln, die hinzugefügt werden muss.

Mark Bessey
quelle