Алгоритм нахождения решения для A xor X = B + X

46

По заданным целым числам A и B найдите целое число X так, чтобы:

  • A, B <2 * 1e18
  • A xor X = B + X

Я очень сомневаюсь, что это уравнение можно решить с помощью математики. Это проблема кодирования, с которой я столкнулся 3 года назад, и даже сейчас я не могу решить ее самостоятельно.

Мой код до сих пор: (это решение грубой силы)

#include <iostream>

using namespace std;

int main()
{

    unsigned long long a, b;
    cin >> a >> b;
    for (unsigned long long x = 1; x < max(a, b); x++) {
        unsigned long long c = a ^ x;
        unsigned long long d = b + x;
        if (c == d) {
            cout << x << endl;
            break;
            return 0;
        }
    }

    cout << -1; //if no such integer exists

    return 0;
}
ааааа
источник
11
Если вы читаете немного больше об эксклюзиве или вы должны найти алгебраическую эквивалентность a xor b = a + b mod 2. Попробуйте немного подумать об этой эквивалентности.
Какой-то программист чувак
16
@Someprogrammerdude Это если a и b - логические переменные, т. Е. 0 или 1, а xor - логическое значение xor. Какая связь с битовым xor?
Джон Кугельман
1
Между прочим, я думаю, что использование грубой силы - это путь, если вы не хотите писать что-то, что может доказать более общие уравнения. Учтите, что вы должны проверить свой код, чтобы убедиться в его правильности, и проще всего было бы протестировать его по алгоритму грубой силы, но тогда вы можете использовать грубую силу в первую очередь. С другой стороны, применение математики в конечном итоге сделает ненужным запуск любого кода.
idclev 463035818
1
@molbdnilo О, один из комментариев предположил, что a xor b = a + b mod 2, и я подумал, что это также относится к целым числам. Я удалю эту часть своего поста.
AAaAa
1
@JohnKugelman Он имел в виду mod 2как в математическом (мод 2), то есть 3 === 7 (мод 2). Дело в том, что вы можете найти уравнение для первого бита X, а затем перейти к следующему биту, где (с учетом переноса) вы получите уравнение для второго бита и т. Д., Как в ответе Даниэля.
Макс Лангоф

Ответы:

45

Обратите внимание, что A + X == (A xor X) + ((A and X)<<1). Так:

A xor X = A + X - ((A and X)<<1) = B + X
A - B = (A and X)<<1

И у нас есть:

(A - B) and not (A<<1) = 0    (All bits in (A - B) are also set in (A<<1))
(A - B)>>1 = A and X

Если условие выполняется, для любого целого числа Y, у которого нет битов, установленных в A, (((A - B) >> 1) или Y) является решением. Если вам нужно только одно решение, вы можете использовать ((A - B) >> 1), где Y = 0. В противном случае решения не существует.

int solve(int a, int b){
    int x = (a - b) >> 1;
    if ((a ^ x) == b + x)
        return x;
    else
        return ERROR;
}
user23013
источник
15
+1. Это означает, что A xor Xэто «добавление без переноса» и ((A and X)<<1)«перенос в добавлении». Поскольку A + Xэто «сложение с переносом», первое уравнение имеет смысл.
полугодие
3
(A and X)<<1в основном 2*(A and X)и потому, что это равно A-Bему, говорит, что проблема может иметь решение, только если A и B оба нечетные или оба события.
Аксиак
1
Я думал, что это как-то связано с вычитанием, но я вовремя не пришел к этому.
SS Anne
38

Это не очень сложно, нужно просто думать мало: предположим , что мы пишем A, Bи Xв двоичном коде и Aᵢэто значение , соответствующее крайнее правое 2 бит.

Мы знаем , что: Aₒ ⊕ Xₒ = Bₒ + Xₒ.

Давайте рассмотрим пример, чтобы узнать, как это оценить: A = 15 и B = 6. Преобразование в двоичный файл:

A = 1 1 1 1           B = 0 1 1 0
X = a b c d           X = a b c d

Теперь у нас есть некоторые возможности. Давайте проанализируем самые правые биты A и B:

1  d = 0 + d

Мы знаем, что dможет быть только 0 или 1, поэтому:

for d = 0
1  d = 0 + d    =>    1  0 = 0 + 0    =>    1 = 0 (not possible)

for d = 1
1  d = 0 + d    =>    1  1 = 0 + 1    =>    0 = 1 (not possible)

Заметно, что XOR ведет себя подобно двоичной сумме (с той разницей, что XOR не создает перенос для следующей битовой суммы):

    XOR           SUM
0  0 = 0  |   0 + 0 = 0
0  1 = 1  |   0 + 1 = 1
1  0 = 1  |   1 + 0 = 1
1  1 = 0  |   1 + 1 = 0

так что не всегда будет возможно найти X, который удовлетворяет A ⊕ X = B + X, потому что нет значения, dкоторое удовлетворяет 1 + d = 0 + d.

В любом случае, если X существует, вы можете просто найти его таким образом, справа налево, находя постепенно.


РАБОЧИЙ ПОЛНЫЙ ПРИМЕР

А = 15, В = 7:

A = 1 1 1 1           B = 0 1 1 1
X = a b c d           X = a b c d

1  d = 1 + d 

Здесь применимы как d = 0, так и d = 1, тогда что? Нам нужно проверить следующий бит. Предположим, что d = 1:

A = 1 1 1 1           B = 0 1 1 1
X = a b c d           X = a b c d

1  d = 1 + d    =>    1  1 = 1 + 1    =>    0 = 0 (possible)

BUT 1 + 1 = 0 generates a carryover for the next bit sum:

Instead of 1  c = 1 + c, we have 1  c = 1 + c (+1) =
                                   1  c = c  (not possible)

поэтому в этом случае d должно быть 0.

carryover                              0
         A = 1 1 1 1           B = 0 1 1 1
         X = a b 0 0           X = a b 0 0
        -----------------------------------
                   0                     0

we know that c must be 0:

carryover                            0 0
         A = 1 1 1 1           B = 0 1 1 1
         X = a b 0 0           X = a b 0 0
        -----------------------------------
                 1 1                   1 1

а как насчет б? нам нужно проверить следующий бит, как всегда:

if b = 0, there won't be a carryover, so we'll have:

1  a = 0 + a  (and this is not possible)

so we try b = 1:

1  b = 1 + b    =>    1  1 = 1 + 1    =>    0 = 0 (with carryover)

а теперь для a:

carryover                          1 0 0
         A = 1 1 1 1           B = 0 1 1 1
         X = a 1 0 0           X = a 1 0 0
        -----------------------------------
               0 0 0                 0 0 0


1  a = 0 + a (+1)    =>    1  a = 1 + a

здесь aмогут быть 0 и 1, но это должно быть 0, чтобы избежать переноса в сумму B + X.

Тогда, X = 0 1 0 0таким образом, X = 4.


КОД

#include <iostream>
using namespace std;

inline int bit(int a, int n) {
    if(n > 31) return 0; 
    return (a & ( 1 << n )) >> n; 
}

int main(){
    int A = 19;
    int B = 7;

    int X = 0;
    int carryover = 0;
    int aCurrent, aNext, bCurrent, bNext;

    for(int i = 0; i < 32; i++){
        aCurrent =  bit(A, i);      bCurrent =  bit(B, i);
        aNext =     bit(A, i + 1);  bNext =     bit(B, i + 1);

        if(aCurrent == 0 && bCurrent == 0){
            if(carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
            }
            carryover = 0;
        }
        else if(aCurrent == 0 && bCurrent == 1){
            if(!carryover) {X = -1; break;}
            if(aNext == bNext){
                X += 1 << i;
            }
            carryover = 1;
        }
        else if(aCurrent == 1 && bCurrent == 0){
            if(!carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
                carryover = 1;
            }
            else {
                carryover = 0;
            }
        }
        else if(aCurrent == 1 && bCurrent == 1){
            if(carryover) {X = -1; break;}
            if(aNext != bNext){
                X += 1 << i;
                carryover = 1;
            }
            else {
                carryover = 0;
            }
        }

    }

    if(X != -1) cout<<"X = "<<X<<endl;
    else cout<<"X doesnt exist"<<endl;

    return 0;
}

Вы можете проверить это здесь .

Даниил
источник