Algorithmus für bitweise Transformation, um eine Gleichung zu erfüllen

Question

Ich habe versucht, herauszufinden, wie man das angehen kann, kann mir jemand eine Idee von einem Algorithmus oder einer Reihe von Schritten geben, um das zu lösen? Ich bin wirklich ratlos. Code ist nicht notwendig. Ich plane, es zu lösen Python3, C und Rust.

Betrachten Sie vier Zahlen: a, b, c und k. Sie müssen höchstens k Bits in a und b ändern, um die Zahlen a 'und b' zu bilden, die die Gleichung a '| erfüllen b '= c. | bezeichnet eine bitweise ODER-Operation.

Wenn kein solcher Wert existiert, geben Sie stattdessen -1 zurück. Im Falle von mehreren Lösungen, machen Sie ein "so klein wie möglich"; Wenn es noch mehrere Lösungen gibt, mache b 'so klein wie möglich.

Wenn die Anzahl der Bits geändert in a ist k.a (ähnlich k.b für b), dann k.a + k.b < = k.

Answer 1

Ich nehme an, die gewünschten Ergebnisse sind XOR-Masken, dh. mit 1-Nummern, wo Bits geändert werden sollte, und 0, wenn sie unberührt gelassen werden soll (so daß a XOR amask = a' und b XOR bmask = b')

Nur der Vollständigkeit halber, hat das Ergebnis der a' | b' 1 Bits, wobei entweder A ‚oder B‘, oder beide haben 1, sonst 0.

Da ist zuerst, unbedingt notwendig, Bedingung für a' | b' = c ist, dass weder ein 'noch b' 1 Bits haben, wo c 0 Bits hat. Mit anderen Worten, um die erste Amask und Bmask zu erhalten, können Sie a und b nehmen und jedes Bit auf 0 setzen, wobei c 1 hat. Mit anderen Worten, um die erste Amask und Bmask zu erhalten, können Sie a und b nehmen und setzen jedes Bit auf 0, wo das binäre Komplement von c 0.

amask = a & (~c) 
bmask = b & (~c) 

Jetzt hat zählen, wie viele Bit sind in 1 und AMASK BMASK (entweder mit einem naiven Schleife oder mit einer der vielen Funktionen PopCount online), und subtrahiere das von deinem k. Wenn k negativ wird, gibt es keine Lösung (return -1).

Der zweite Teil erfordert, dass Sie Bits finden, wo sowohl a als auch b 0 sind, aber c ist 1.Um es kurz:
temp_mask = c & ((a XOR amask) | (b XOR bmask))
temp_mask sind die Bits müssen Sie 1 in entweder a oder b setzen (die man auf den „kleinsten“ Anforderung hängt Aber zuerst, Pop-count temp_mask auch, wenn das Ergebnis. größer ist als weitere k ist, gibt es keine Lösung ist (-1 zurück)

Der nächste Schritt ist einfach:.
amask = amask | temp_mask
Der bisherige AMASK 1 hat, wo c 0 ist, nun diese Aussage wird nichts überlappen .

Jetzt haben Sie mindestens eine Lösung für a' | b' = c, das ist
(a XOR amask) | (b XOR bmask) = c
Aber da könnte noch eine andere mit einer kleineren a sein, oder?

Das ist auch nicht sehr schwer: Jedes Bit, das 1 in (a XOR amask) ist, aber 0 in (b XOR bmask) kann "bewegt" werden, dh. mach es 0 in (a XOR amask) und 1 in (b XOR bmask). Das Ergebnis c wird gleich sein, aber der numerische Wert von (a XOR amask) wird kleiner sein (möglicherweise bleibt er im schlimmsten Fall gleich).

temp_mask = (a XOR amask) & (~(b XOR bmask)) 
amask = amask XOR temp_mask 
bmask = bmask XOR temp_mask 

Um dies zu implementieren, achten Sie auf unsigned und Int-Größen.

Voll Pseudo-Code:

amask = a & (~c) 
bmask = b & (~c) 
temp_mask = c & ((a XOR amask) | (b XOR bmask)) 
amask = amask | temp_mask 
temp_mask = (a XOR amask) & (~(b XOR bmask)) 
amask = amask XOR temp_mask 
bmask = bmask XOR temp_mask 

Answer 2

Der langsame Weg:

• Iterate alle Bits.
• Wenn ein Bit in a oder b gesetzt ist, aber nicht in c, setze es in a 'und b' zurück (Anzahl: 1 oder 2).
• Wenn es in c, aber nicht in beiden, a und b, gesetzt ist, setzen Sie es in b '(count: 1).

Machen Sie es schnell mit diesen Daten:

• zusätzliche Bits in a finden: a & ~ c (müssen in jedem Fall entfernt werden)

• Finden zusätzliche Bits in b: b & ~ c (müssen in jedem Fall entfernt werden)

• Finden fehlende Bits: ~ (a | b) & c (müssen in b zu setzen 'zu halten, eine' kleine)

Möglich, wenn die Summe der entsprechenden Bitanzahl < = k ist.