23

I have spent the last 5 hours searching for an answer. Even though I have found many answers they have not helped in any way.

What I am basically looking for is a mathematical, arithmetic only representation of the bitwise XOR operator for any 32bit unsigned integers.

Even though this sounds really simple, nobody (at least it seems so) has managed to find an answer to this question.

I hope we can brainstorm, and find a solution together.

Thanks.

7
  • 1
    possible duplicate of XOR using mathematical operators
    – Matt Ball
    Jan 22, 2014 at 20:29
  • 7
    Absolutely no duplicate, as the linked thread provides NO USEFUL INFORMATION whatsoever. Jan 22, 2014 at 20:31
  • @Pietu: So why can I model a bitwise rotation with mathematics? There certainly must be a way until its proven it can't be done. This has not yet been proven to my knowledge. Jan 22, 2014 at 20:32
  • Bitwise rotation is a special case of how multiplication (and division) works in binary, as it works the same as multiplying/dividing by 2. This is the same: if you rotate a decimal integer left and add a 0, what happens? It is multiplied by 10, the base number (similarly 2 in binary). Jan 22, 2014 at 20:35
  • @user3170842, first consider how you can represent a number as a series of bits using a summation over the series. Once you have the two operands in that representation, you can use the equations in the 'useless' answers here to compute an XOR for each individual bit. It might help to know the context of what you're trying to do with this, though, as the nature of the problem most often drives the best choice of representation in mathematics.
    – Dan Bryant
    Jan 22, 2014 at 20:46

9 Answers 9

36

XOR any numerical input between 0 and 1 including both ends

a + b - ab(1 + a + b - ab)

XOR binary input

a + b - 2ab or (a-b)²


Derivation

Basic Logical Operators

NOT = (1-x)

AND = x*y

From those operators we can get...

OR = (1-(1-a)(1-b)) = a + b - ab

Note: If a and b are mutually exclusive then their and condition will always be zero - from a Venn diagram perspective, this means there is no overlap. In that case, we could write OR = a + b, since a*b = 0 for all values of a & b.


2-Factor XOR

Defining XOR as (a OR B) AND (NOT (a AND b)):

(a OR B) --> (a + b - ab)

(NOT (a AND b)) --> (1 - ab)

AND these conditions together to get...

(a + b - ab)(1 - ab) = a + b - ab(1 + a + b - ab)

enter image description here

Computational Alternatives

If the input values are binary, then powers terms can be ignored to arrive at simplified computationally equivalent forms.

a + b - ab(1 + a + b - ab) = a + b - ab - a²b - ab² + a²b²

If x is binary (either 1 or 0), then we can disregard powers since 1² = 1 and 0² = 0...

a + b - ab - a²b - ab² + a²b² -- remove powers --> a + b - 2ab

XOR (binary) = a + b - 2ab

Binary also allows other equations to be computationally equivalent to the one above. For instance...

Given (a-b)² = a² + b² - 2ab

If input is binary we can ignore powers, so...

a² + b² - 2ab -- remove powers --> a + b - 2ab

Allowing us to write...

XOR (binary) = (a-b)²


Multi-Factor XOR

XOR = (1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)

Excel VBA example...

Function ArithmeticXOR(R As Range, Optional EvaluateEquation = True)

Dim AndOfNots As String
Dim AndGate As String
For Each c In R
    AndOfNots = AndOfNots & "*(1-" & c.Address & ")"
    AndGate = AndGate & "*" & c.Address
Next
AndOfNots = Mid(AndOfNots, 2)
AndGate = Mid(AndGate, 2)

'Now all we want is (Not(AndGate) AND Not(AndOfNots))
ArithmeticXOR = "(1 - " & AndOfNots & ")*(1 - " & AndGate & ")"
If EvaluateEquation Then
    ArithmeticXOR = Application.Evaluate(xor2)
End If

End Function

Any n of k

These same methods can be extended to allow for any n number out of k conditions to qualify as true.

For instance, out of three variables a, b, and c, if you're willing to accept any two conditions, then you want a&b or a&c or b&c. This can be arithmetically modeled from the composite logic...

(a && b) || (a && c) || (b && c) ...

and applying our translations...

1 - (1-ab)(1-ac)(1-bc)...

This can be extended to any n number out of k conditions. There is a pattern of variable and exponent combinations, but this gets very long; however, you can simplify by ignoring powers for a binary context. The exact pattern is dependent on how n relates to k. For n = k-1, where k is the total number of conditions being tested, the result is as follows:

c1 + c2 + c3 ... ck - n*∏

Where c1 through ck are all n-variable combinations.

For instance, true if 3 of 4 conditions met would be

abc + abe + ace + bce - 3abce

This makes perfect logical sense since what we have is the additive OR of AND conditions minus the overlapping AND condition.

If you begin looking at n = k-2, k-3, etc. The pattern becomes more complicated because we have more overlaps to subtract out. If this is fully extended to the smallest value of n = 1, then we arrive at nothing more than a regular OR condition.


Thinking about Non-Binary Values and Fuzzy Region

The actual algebraic XOR equation a + b - ab(1 + a + b - ab) is much more complicated than the computationally equivalent binary equations like x + y - 2xy and (x-y)². Does this mean anything, and is there any value to this added complexity?

Obviously, for this to matter, you'd have to care about the decimal values outside of the discrete points (0,0), (0,1), (1,0), and (1,1). Why would this ever matter? Sometimes you want to relax the integer constraint for a discrete problem. In that case, you have to look at the premises used to convert logical operators to equations.

When it comes to translating Boolean logic into arithmetic, your basic building blocks are the AND and NOT operators, with which you can build both OR and XOR.

OR = (1-(1-a)(1-b)(1-c)...)

XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)

So if you're thinking about the decimal region, then it's worth thinking about how we defined these operators and how they behave in that region.

Non-Binary Meaning of NOT

We expressed NOT as 1-x. Obviously, this simple equation works for binary values of 0 and 1, but the thing that's really cool about it is that it also provides the fractional or percent-wise compliment for values between 0 to 1. This is useful since NOT is also known as the Compliment in Boolean logic, and when it comes to sets, NOT refers to everything outside of the current set.

Non-Binary Meaning of AND

We expressed AND as x*y. Once again, obviously it works for 0 and 1, but its effect is a little more arbitrary for values between 0 to 1 where multiplication results in partial truths (decimal values) diminishing each other. It's possible to imagine that you would want to model truth as being averaged or accumulative in this region. For instance, if two conditions are hypothetically half true, is the AND condition only a quarter true (0.5 * 0.5), or is it entirely true (0.5 + 0.5 = 1), or does it remain half true ((0.5 + 0.5) / 2)? As it turns out, the quarter truth is actually true for conditions that are entirely discrete and the partial truth represents probability. For instance, will you flip tails (binary condition, 50% probability) both now AND again a second time? Answer is 0.5 * 0.5 = 0.25, or 25% true. Accumulation doesn't really make sense because it's basically modeling an OR condition (remember OR can be modeled by + when the AND condition is not present, so summation is characteristically OR). The average makes sense if you're looking at agreement and measurements, but it's really modeling a hybrid of AND and OR. For instance, ask 2 people to say on a scale of 1 to 10 how much do they agree with the statement "It is cold outside"? If they both say 5, then the truth of the statement "It is cold outside" is 50%.

Non-Binary Values in Summary

The take away from this look at non-binary values is that we can capture actual logic in our choice of operators and construct equations from the ground up, but we have to keep in mind numerical behavior. We are used to thinking about logic as discrete (binary) and computer processing as discrete, but non-binary logic is becoming more and more common and can help make problems that are difficult with discrete logic easier/possible to solve. You'll need to give thought to how values interact in this region and how to translate them into something meaningful.


2
  • 2
    Your answer is important for me.
    – Land
    Apr 6, 2021 at 12:45
  • 2
    The words "XOR any numerical input" at the top are a bit misleading, since you can't use this formula to XOR two arbitrary 32-bit values. Applying that equation to the values 3 and 5 produces a result of 98, rather than the 6 expected by bitwise XOR'ing them.
    – Desty
    Dec 31, 2021 at 2:43
1

"mathematical, arithmetic only representation" are not correct terms anyway. What you are looking for is a function which goes from IxI to I (domain of integer numbers).
Which restrictions would you like to have on this function? Only linear algebra? (+ , - , * , /) then it's impossible to emulate the XOR operator.
If instead you accept some non-linear operators like Max() Sgn() etc, you can emulate the XOR operator with some "simpler" operators.

2
  • FYI, mathematicians usually use Z for the integer numbers. I is sometimes the irrational numbers, although that is far less common.
    – Teepeemm
    Jan 23, 2014 at 0:57
  • 1
    @user3042724, why it's impossible? May 23, 2016 at 14:00
1

Given that (a-b)(a-b) quite obviously computes xor for a single bit, you could construct a function with the floor or mod arithmetic operators to split the bits out, then xor them, then sum to recombine. (a-b)(a-b) = a2 -2·a·b + b2 so one bit of xor gives a polynomial with 3 terms.

Without floor or mod, the different bits interfere with each other, so you're stuck with looking at a solution which is a polynomial interpolation treating the input a,b as a single value: a xor b = g(a · 232 + b)

The polynomial has 264-1 terms, though will be symmetric in a and b as xor is commutative so you only have to calculate half of the coefficients. I don't have the space to write it out for you.

1

I wasn't able to find any solution for 32-bit unsigned integers but I've found some solutions for 2-bit integers which I was trying to use in my Prolog program. One of my solutions (which uses exponentiation and modulo) is described in this StackOverflow question and the others (some without exponentiation, pure algebra) can be found in this code repository on Github: see different xor0 and o_xor0 implementations.

The nicest xor represention for 2-bit uints seems to be: xor(A,B) = (A + B*((-1)^A)) mod 4.

Solution with +,-,*,/ expressed as Excel formula (where cells from A2 to A5 and cells from B1 to E1 contain numbers 0-4) to be inserted in cells from A2 to E5:

(1-$A2)*(2-$A2)*(3-$A2)*($A2+B$1)/6 - $A2*(1-$A2)*(3-$A2)*($A2+B$1)/2 + $A2*(1-$A2)*(2-$A2)*($A2-B$1)/6 + $A2*(2-$A2)*(3-$A2)*($A2-B$1)/2 - B$1*(1-B$1)*(3-B$1)*$A2*(3-$A2)*(6-4*$A2)/2 + B$1*(1-B$1)*(2-B$1)*$A2*($A2-3)*(6-4*$A2)/6

1

It may be possible to adapt and optimize this solution for 32-bit unsigned integers. It's complicated and it uses logarithms but seems to be the most universal one as it can be used on any integer number. Additionaly, you'll have to check if it really works for all number combinations.

0

I do realize that this is sort of an old topic, but the question is worth answering and yes, this is possible using an algorithm. And rather than go into great detail about how it works, I'll just demonstrate with a simple example (written in C):

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>   
    #include <time.h>

    typedef unsigned long
            number;

    number XOR(number a, number b)
    {
            number
                    result = 0,
            /*
                    The following calculation just gives us the highest power of 
                    two (and thus the most significant bit) for this data type.
            */          
                    power = pow(2, (sizeof(number) * 8) - 1);
    /*
            Loop until no more bits are left to test...
    */                
            while(power != 0)
            {
                    result *= 2;
            /*
                    The != comparison works just like the XOR operation.
            */                
                    if((power > a) != (power > b))
                            result += 1;
                    a %= power;
                    b %= power;
                    power /= 2;
            }
            return result;
    }

    int main()
    {
            srand(time(0));
            for(;;)
            {
                    number
                            a = rand(), 
                            b = rand();
                    printf("a = %lu\n", a);
                    printf("b = %lu\n", b);
                    printf("a ^ b     = %lu\n", a ^ b);
                    printf("XOR(a, b) = %lu\n", XOR(a, b));
                    getchar();
            }
    }
0

I think this relation might help in answering your question

A + B = (A  XOR  B ) + 2*(A.B) 
1
  • This is the identity A + B = (A XOR B) + 2 (A AND B). A AND B gives the bits that carry in a base two sum. A XOR B is A + B but in GF(2) if I'm using terminology correctly (means that for each bit of A and B, sum and compute the residue modulo 2). It helps, but not much.
    – AMDG
    Sep 23, 2023 at 15:06
0

The OEIS is the discrete algorithmist's best friend. Pro tip.


  1. XOR is conditional negation:

Given x XOR y, x, y ∈ positive integers, x XOR y = NOT y iff x = 2**ceil(log_2(y+1)) - 1; and the converse also holds, i.e., for x XOR y = NOT x.

  1. In binary, the residue modulo two for 2 - x and 1 - x yields XOR for x ∈ {0, 1} respectively, meaning 2 - x can be used for computing the identity of x, while 1 - x can be used for computing the negation of x:

For two:

10 - 01 = 01 congruent to 1 modulo 2

10 - 00 = 10 congruent to 0 modulo 2

For one:

01 - 01 = 00 congruent to 0 modulo 2

01 - 00 = 01 congruent to 1 modulo 2

  1. Given x and y that we wish to XOR, as we have already shown above, XOR is conditional negation; and in statement (2), we gave two expressions for evaluating the identity and logical negation of a number. For simplicity's sake, we will work with x XOR y = NOT y.

In this case, the bit corresponding to the 2^i-th digit being a 1 in x means we should negate the 2^ith digit in y; and being a 0 in x means we should compute the identity of the corresponding digit in y (i.e., leave unchanged).

  1. In base 2, 2 requires two digits, but in base 4, 2 is one digit, and is directly representable in base 2.

  2. The Moser-de Bruijn sequence ( https://oeis.org/A000695 ) is the positive integers expressed in base 4. Here's how you construct it given some positive integer n in binary, and a(n) | n ∈ positive integers being this sequence:

a(0) = 00

a(1) = 01

a(10) = 01 00

a(11) = 01 01

a(100) = 01 00 00

and so forth

  1. NOT(x) is congruent to -x which is the basis for so-called "two's complement signed integers" in our domain: NOT(x) = (2**ceil(log_2(x+1)) - 1) - x.

  2. The following therefore holds true for all x,y ∈ positive integers, letting b(n) such that b(a(n)) = n:

x XOR y = b(AND(a(x) + a((2**ceil(log_2(x+1)) - 1) - x) - a(y)), a((2**ceil(log_2(x+1)) - 1) - x))

where presumably the AND given above has a closed form somewhere that can be used since we're ANDing with a very regular form of numbers (as you can see, it's ANDing with 1111... with its bits spread to 01010101...), i.e., the result of this particular AND with the positive integers is sequence https://oeis.org/A063695 , but I'm not aware of such at the time of writing this.

This is only one such possible purely mathematical definition (see the formulas section on the OEIS for the sequence and find something suitable if you can, but I'm not happy with the given closed forms at the time of writing as I want a closed form with O(1) operations), however, there is a simple method which requires the ability to AND via a sequence of indefinite 01s (or 10s) concatenated indefinitely that seems like a plausible lead which I have yet to figure out at the time of writing this. I will cover this in the future in a new section below if anything should come of it.

-2

(a-b)*(a-b) is the right answer. the only one? I guess so!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.