当前位置: 动力学知识库 > 问答 > 编程问答 >

math - Mathematical (Arithmetic) representation of XOR

问题描述:

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.

网友答案:

"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.

网友答案:

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.

网友答案:

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

网友答案:

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

网友答案:

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.

网友答案:

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();
            }
    }
分享给朋友:
您可能感兴趣的文章:
随机阅读: