math - 2 つの数値の XOR と SUM が与えられます。数字を見つける方法は？

Question

2 つの数値の XOR と SUM が与えられます。数字を見つける方法は？たとえば、x = a+b、y = a^b; x、y が与えられた場合、a、b を取得する方法は? また、できない場合はその理由を教えてください。

Answer 1

これは確実に行うことはできません。単一の反例は理論を破壊するのに十分であり、あなたの場合、その例は0, 100と4, 96. これらの合計100と xorの両方100も同様です。

  0 = 0000 0000            4 = 0000 0100
100 = 0110 0100           96 = 0110 0000
      ---- ----                ---- ----
xor   0110 0100 = 100    xor   0110 0100 = 100

したがって、 の合計100と の xor が与えられた場合、どの可能性がその状況を生成したかを100知ることはできません。

価値があるのは、このプログラムは数字だけで可能性をチェックすることです0..255:

#include <stdio.h>

static void output (unsigned int a, unsigned int b) {
    printf ("%u:%u = %u %u\n", a+b, a^b, a, b);
}

int main (void) {
    unsigned int limit = 256;
    unsigned int a, b;
    output (0, 0);
    for (b = 1; b != limit; b++)
        output (0, b);
    for (a = 1; a != limit; a++)
        for (b = 1; b != limit; b++)
            output (a, b);
    return 0;
}

次に、その出力を取得してマッサージし、繰り返されるすべての可能性を提供します。

testprog | sed 's/ =.*$//' | sort | uniq -c | grep -v ' 1 ' | sort -k1 -n -r

これは次を与えます:

255 255:255
128 383:127
128 319:191
128 287:223
128 271:239
128 263:247
:
and so on.

その縮小されたセットでも、同じ合計と xor を生成するかなりの数の組み合わせがあり、最悪の場合、 の合計/xor を生成する可能性が多数255/255あります。

255:255 = 0 255
255:255 = 1 254
255:255 = 2 253
255:255 = <n> <255-n>, for n = 3 thru 255 inclusive

Answer 2

a , b の合計 = a+b = (a^b) + (a&b)*2 がある場合、この式が役立つ場合があります。