Wie kann ich die Mindestanzahl finden, die erforderlich ist, um eine Sequenz hinzuzufügen, so dass ihr Xor Null wird

  • Wenn Sie eine Folge von natürlichen Zahlen haben, können Sie jeder Zahl in der Folge eine beliebige natürliche Zahl hinzufügen, sodass deren Xoder Null werden. Mein Ziel ist es, die Summe der hinzugefügten Zahlen zu minimieren.

    Beachten Sie die folgenden Beispiele:

    1. Für $ 1, 3 $ lautet die Antwort $ 2 $; Hinzufügen von $ 2 $ zu $ ​​1 $ ergibt $ 3 \ oplus 3 = 0 $.

    2. Für $ 10, 4, 5, 1 $ lautet die Antwort $ 6 $; Durch Hinzufügen von $ 3 $ zu $ ​​10 $ und $ 3 $ zu $ ​​5 $ erhalten wir $ 13 \ oplus 4 \ oplus 8 \ oplus 1 = 0 $.

    3. Für $ 4, 4 $ Die Antwort ist $ 0 $, da $ 4 \ oplus 4 = 0 $ ist.

    Ich habe versucht, an binären Darstellungen der Sequenznummer zu arbeiten, aber es so komplex geworden. Ich möchte wissen, ob es eine einfache und effiziente Möglichkeit gibt, dieses Problem zu lösen.

    09 June 2014
    Kyle JonesPravin Gadakh
2 answers
  • Mir scheint, dass $ a = a_i \ oplus \ dots \ oplus a_n $ alle notwendigen Informationen enthält: Die $ 1 $ -Bits in $ a $ sind die Bits, die Sie benötigen, um (genau) eines der $ a_i $. Da Sie nur hinzufügen dürfen, müssen Sie ein $ a_i $ suchen, bei dem das entsprechende Bit $ j $ $ 0 $ ist, und es umdrehen - dies verursacht die gleichen Kosten für alle $ a_i $ ist $ 2 ^ j $, also spielt die Wahl keine Rolle. Das Problem beginnt, wenn es kein $ a_i $ gibt.

    Deshalb müssen Sie dies iterativ tun und vom niedrigstwertigen Bit aufwärts arbeiten. Verfahren Sie wie oben beschrieben. Wenn es kein geeignetes $ a_i $ gibt, wählen Sie das $ a_i $ mit der maximalen Anzahl von $ 1 $ Bits von der aktuellen Position aus - dies erhöht die Chance, in zukünftigen Iterationen einen geeigneten Kandidaten zu finden -, dreht das Bit und überträgt es , das ist, drehen Sie alle Einsen nach links, bis Sie eine Null zu einer Eins machen. Beachten Sie, dass wir immer noch $ 2 ^ j $) hinzufügen. Da sich der Übertrag nur nach links ausbreitet, werden frühere Auswahlmöglichkeiten nicht ungültig. $ A $ neu berechnen und mit $ j + 1 $ fortfahren; iterieren, bis Sie $ a = 0 $ haben.

    Beachten Sie, dass dies, soweit ich das beurteilen kann, nur eine Heuristik ist: Die Wahl von $ i $ kann suboptimal sein, wenn es viele verursacht Bits in $ a $ werden nicht Null. Ich bin nicht sicher, ob dies vermieden werden kann.

    04 July 2012
    Raphael
  • Ich habe eigentlich keine Lösung, aber hier sind ein paar Ideen, die aufkamen:

    Betrachten Sie die Ergebnisse aller XOR-Ergebnisse In der Reihenfolge gibt dies eine Obergrenze für die Anzahl der erforderlichen Ergänzungen. In Ihrem Beispiel von $ 10, 4, 5, 1 $ haben wir beispielsweise $ 10 \ oplus 4 \ oplus 5 \ oplus 1 = 10 $. Sie wissen also, dass Sie nicht mehr als $ 8 $ hinzufügen müssen (weil die 8 -bit ist der höchste Satz). Das Verteilen von bis zu acht "Einsen", die auf vier Arten verteilt sind, ist eine recht kleine Anzahl von Kombinationen. Ich kann mich nicht so spät in der Nacht an diese Formel erinnern, aber irgendwo ist ein $ n! $ Drin.

    Um diese Aussage ein wenig mehr zu verdeutlichen, betrachten Sie beliebige Zahlen $ A, B $ wie $ A \ oplus B = 8 $. Die Bits, die höher als Bit 3 sind, werden offensichtlich alle aufgehoben, sodass Sie sie ignorieren können. Für die unteren vier Bits ist XOR gleich 8, also ist der schlechteste mögliche Fall (in Bezug auf die Anzahl der hinzuzufügenden Einsen), wenn $ A = 8 $ und $ B = 0 $ (alle Nullen außer dem höchsten Bit). denn Sie müssen +8 zu B hinzufügen, um das oberste Bit gesetzt zu bekommen. Wenn in einer der Zahlen irgendein ein Bit gesetzt ist, müssen Sie weniger hinzufügen.

    Vielleicht können Sie davon ausgehen und eine engere Zahl entwickeln maximal hinzuzufügender Betrag.

    04 July 2012
    Raphael