2つの数字の排他的論理和と和を考えると、それらを満たすペアの数を見つける方法は？

Question

私は質問が少し混乱するかもしれないと思う。だから私は最初にそれを説明しようとします。

2つの数字のXORとSUMが与えられているとします。

たとえば、XORが5であり、SUMが9である場合、SUMとXORを満たす4のペアがあります。それらは(2, 7),(3, 6),(6, 3),(7, 2)です。従って2+7=9および2^7=5。

SUMとXORを満たす数字の番号を探したいだけです。したがって、私が答えた例では4で十分です。どのペアがそれらを満たすかを知る必要はありません。

私はhereからこの問題を取りました。

回答hereを確認しました。それは十分ではないO（n）解を提供する。

この問題の解決方法を示す論説があります。これはhereです。

問題は、私は解決策を理解することができないということです（627Aの解決策を探してください）。 （そこに2つの数aがあり、B場合）、その後、 a+b = (a XOR b) + (a AND b)*2

がどのように私はそれに到着したのですか？私は
、彼らはこのような式を使用まとめることができるものから残りのステップは私には不明です。

誰かがこの問題を解決する方法や解決策を説明する方法があれば、助けてください。

Answer 1

あなたは2進加算を行う際に正確に何が起こるとしてa+b = (a XOR b) + (a AND b)*2を考えます。あなたの例から、a = 010とb = 111：ビットごとに

010 
111 
--- 
1001 = 101 + 100 

、あなたは正確にa XOR bプラス前回からのキャリーインビットであるaとb（0+0=0、0+1=1、1+0=1、1+1=0、からのビットを追加つまり、aとbの前のビットが両方とも1であれば、それも正確に(a AND b)*2です（2を乗算すると左にシフトします）。

その式で、a AND bを計算することができます。

ここで、希望する数値を数えるために、a XOR bとa AND bの各ビットを1つずつ見て、すべての可能性を掛けます。 a[i] XOR b[i] = 0とa[i] AND b[i] = 0場合a[i] = b[i] = 0その後、

• （私はaのi番目のビットのためa[i]を書いてみましょう）。このビットの可能性は1つだけです。

• a[i] XOR b[i] = 0およびa[i] AND b[i] = 1の場合は、a[i] = b[i] = 1です。このビットの可能性は1つだけです。

• a[i] XOR b[i] = 1およびa[i] AND b[i] = 0の場合、a[i] = 1およびb[i] = 0またはその逆。 2つの可能性。

• a[i] XOR b[i] = 1とa[i] AND b[i] = 1を使用することはできません。

あなたの例では、a XOR b = 101とa AND b = 010です。私たちは答えは2*1*2 = 4です。

Answer 2

a AND bは数字の両方にあるビットです。したがって、これらは合計で2倍になります。 a XOR bは、数字の1つにしか存在しないビットであるため、これらは合計で1回カウントする必要があります。ここ

は一例であり：

• a = 4 = 1*2^2 + 0*2^1 + 0*2^0 (or just 100)
• b = 13 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 (or just 1101)
• a + b = (1*2^2 + 0*2^1 + 0*2^0) + (1*2^3 + 1*2^2 + 0*2^1 + 1*2^0) = 1*2^3 + 2*2^2 + 0*2^1 + 1*2^0

ノート番号（2^2）の両方にあるビットが二度カウントされる方法を最後の行に残りは一度しかカウントされません！あなたはすべてのペアを見つける必要があなたの問題を解決するために

（a、b）は合計に集計しています。あなたがしたいことはこれです：

1. SUMからXOR値を引きます。あなたは2*(a AND b)のままです。
2. 2で割ります。これで、aとbの両方で設定する必要があるすべてのビットが得られました。
3. あなたはXOR値を持っているので、あなたはビットがに正確に一つの aとbを設定する必要があります正確に何を知っている、とあなただけの計算値は、それらの両方に設定する必要がありますビットですながらします。したがって、ビットをaまたはbにそれぞれ設定するすべての順列をリストします。

私の前の例を続行するには：我々は、これらの順列を得る

• a AND b = 0100（常に両方で設定）
• a XOR b = 1001（私たちはこれらのすべての順列を試してみる必要があります）

をソリューション：

• a = 0100 + 0000 = 0100, b = 0100 + 1001 = 1101 => (4, 13)
• a = 0100 + 0001 = 0101, b = 0100 + 1000 = 1100 => (5, 12)
• a = 0100 + 1000 = 1100, b = 0100 + 0001 = 0101 => (12, 5)
• a = 0100 + 1001 = 1101, b = 0100 + 0000 = 0100 => (13, 4)