Get unknown values from XOR results

[novice007]

Hi,
Assume we don't know the values of a, b and c but we have the results of 'a XOR c' and 'b XOR c'. How could we know the values of a, b and c? It should not be only XOR operation, it could be any other operation, but my main question is- knowing the results only, how could we get the unknown values where both results have one similar variable, like 'c' here?

/novice007

[Intrade]

For one, which operations are allowed? You said "any" operation, but are we talking strictly binary, or any kind of operation between a, b and c?

Also notice the immediate difficulty of using XOR alone - if a, b and c are all the same number, how can you possible find the solution? Any number XOR'd with itself will be zero.

Are there restrictions on a, b and c (are they completely different numbers, or is a > b > c or c > b > a or what? ) ?

[novice007]

Hi,
a, b and c are always different values, random values which are not same. They are also binary values. I said any operation that means other logical operations like AND, OR, NOR, NOT etc. For example, it could be 'a AND c' and 'b XOR c'. I don't mind if two have different binary operations or doing unary operation of one variable before putting it in binary operation, like 'b XOR (!c)'.

My intention is- I have two results and I know what operations are done to create those results, also I know both results contain the same variable 'c'. How could I get a, b and c? That means in which way I can create the results, so that later I could get the values of variables from the results without knowing a, b and c but the operations.

/novice007

[Intrade]

To make things more visual to find a solution, you could use concepts of propositions and sets combined, and treat a number as a set of binary values at a particular position.

Using 3, 4 and 5 as examples, where the left point-position is the binary value and the right point-position is the position the value exists for a 'number set'...

a = 3, b = 4 and c = 5.

a = 3 = 011 in binary
b = 4 = 100 in binary
c = 5 = 101 in binary

a = 3 = { (1, 0), (1, 1) }
b = 4 = { (1, 2) }
c = 5 = { (1, 0), (1, 2) }

Before operating on the above values, let's try to make some reasonable deductions on potential cases using familiar binary operations.

If we know the result of a XOR c, then we know that the result is a set that consists of binary elements that exist in either a or c, but not both.

If a AND c result contains no elements (or, its zero), and a OR c is not zero, then neither a nor c have common binary elements. We can assume that the result of a OR c will be either a, c or a number greater than both due to the combination of binary elements for the result.

Assuming that unary operations are acceptable, the compliment of a set combined with the set itself will result in the universal set of potential binary values that the set can consist of.

If this is true, we have some more information on individual sets. For example, if a AND c is zero, but a OR b is not zero, then we can assume that some of the elements of ~c exist within a, and vice versa.

From the above values, a is 011 and b is 100, a XOR b is 111 or 6 but a AND b is 0. Assuming that the compliment of either a or b consists of potential points for both, a should be a subset of b's compliment and vise versa. Meaning, a is or exists within ~b.

We can find a simply by knowing if a AND b is zero. If a AND b is zero, a exists within ~b, which means you can find a by the operation of a AND ~b. In addition you can find b from a's compliment. b is the same as ~a AND b.

Numerically speaking, b is 100 and ~b is 011. In this example, it just so happens that ~b is a, but this is just a coincidence.

[thoughtcoder]

There's no way to find the answer: you do not have enough information. You only have 2N bits of information, where N is the size of the integer types involved, measured in bits. It takes 3N bits to describe the values of a, b, and c.

[Intrade]

I wrote this program hoping that it would examplify this issue a bit better.

#include <iostream>
#include <ctime>
#include <string>
#include <cmath>

#define OR |
#define NOT ~
#define AND &
#define XOR ^

using std::cout;
using std::endl;
using std::time_t;
using std::cin;
using std::string;

const char* const TRUE = "TRUE";
const char* const FALSE = "FALSE";
const char* toName(bool);
string getBitValue(int);

int main(){
    
    srand( static_cast<unsigned int>(time(0)) );
    
    // input
    int a = rand()%4;
    int b = rand()%5;
    int c = rand()%6;
    
    // showing the values for test-purposes
    cout << "a: " << a << " : " << getBitValue(a) << endl;
    cout << "b: " << b << " : " << getBitValue(b) << endl;
    cout << "c: " << c << " : " << getBitValue(c) << endl;
    cout << "\n\n\n" << endl;
    
    //results
    int a_or_b = a OR b;
    int a_or_c = a OR c;
    int b_or_c = b OR c;
    int a_or_nb = a OR (NOT b);
    int a_or_nc = a OR (NOT c);
    int b_or_nc = b OR (NOT c);
    int a_xor_b = a XOR b;
    int a_xor_c = a XOR c;
    int b_xor_c = b XOR c;
    int a_xor_nb = a XOR (NOT b);
    int a_xor_nc = a XOR (NOT c);
    int b_xor_nc = b XOR (NOT c);
    int a_and_b = a AND b;
    int a_and_c = a AND c;
    int b_and_c = b AND c;
    int a_and_nb = a AND (NOT b);
    int a_and_nc = a AND (NOT c);
    int b_and_nc = b AND (NOT c);
    
    // in theory, a should be a AND ~b + a AND b
    int assumed_a = a_and_nb OR a_and_b;
    cout << "a should be " << (assumed_a) << endl;
    
    // once a is found, we should easily be able to find b and c
    
    // b is a OR b - a + a AND b
    cout << "b should be " << ( a_or_b - assumed_a + a_and_b ) << endl;
    
    // c can be found a similar way--
    cout << "c should be " << ( a_or_c - assumed_a + a_and_c ) << endl;
    
    cin.get();
    
    return 0;
}

// for test purposes
const char* toName(bool value){
      return (value) ? TRUE : FALSE;
}

// for test purposes
string getBitValue(int value){
       
       string s;
       
       bool start = false;

       for(int i = static_cast<int>( log(INT_MAX) / log(2) ); i >= 0; i--){
               bool hasPosition = ( (1 << i) AND value );
               if(hasPosition)
                               start = true;
               if(start)
                        s.append(1, ( ( hasPosition ) ? '1' : '0') );
       }
       
       return s;
}