This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[dirvine]

NUM_SIZE=32

A XOR B

for n=0 to n=32; 2^n * (((A/2^n) % 2) + (B/2^n) %2) %2)

Probably easier for me though to have written a for loop.



13YSCv8SLrBw27AdyRQY8adfsGa56viQcJ

[Evil-Knievel]

This message was too old and has been purged

[dirvine]

NUM_SIZE=32

A XOR B

for n=0 to n=32; 2^n * (((A/2^n) % 2) + (B/2^n) %2) %2)

Probably easier for me though to have written a for loop.



13YSCv8SLrBw27AdyRQY8adfsGa56viQcJ

Hey, thanks for your answer and your intrest. However a purely arithmetic solution is search. The for loop actually is more than just maths which prevents it from putting the formula into a CAS to process it any further. Also only modulus 2^32-1 is allowed ... unfortunately there is a mod 2 in your equation.

But this idea is pretty good, I hope you come up with a pure mathematical/algebraic representation soon.  

Yes I spotted the mod statement and also signed numbers too after posting. I will have a wee think now :-) cheers for the question it's pretty cool.

[niniyo]

How is this?

Sum from n = 1 to 32:
  (((a mod 2^n) / 2^(n-1)) * 2^(n-1)) + (((b mod 2^n) / 2^(n-1)) * 2^(n-1))

I don't quite understand what you mean about only being able to use modulus 2^32-1?  Isn't 2^32-1 the maximum number, so anything mod that would just give the same number back?

[Evil-Knievel]

This message was too old and has been purged

[niniyo]

OK how about this:

function mymod (value, modpow) =>
  ; returns the 32-bit result of value mod 2^modpow
  ((value * 2^(32-modpow) MOD 2^32) / 2^(32-modpow));


; note that the above is a mathematical expression, and i'm just going to use it like a macro to avoid repeating the same expression all the time

function myxor (a, b) =>
  ; return the 32-bit result of a bitwise xor b
  sum from n = 1 to 32:
    mymod(mymod(a,n) / 2^(n-1) * 2^(n-1) + mymod(a,n) / 2^(n-1) * 2^(n-1), n)

EDIT: I used the expression ((n / 2^n) * 2^n) to zero out the lowest n bits, because I'm assuming these are integer operations so a division results in the truncated integer result.  Is that suitable?

[BurtW]

Code:

#include <iostream> 
#include <stdio.h> 

using namespace std; 

int main (int argc, char *argv[]) 
{ 
    unsigned long a = 0x01234567ul; 
    unsigned long b = 0x87654321ul; 
    unsigned long x = 0; 
    unsigned long d = 1; 
    unsigned long n, r; 

    for (n=0; n<32; n++) { 
        r = a + b; 
        r *= 2147483648ul; 
        r /= (2147483648ul/d); 
        x += r; 
        a /= 2; 
        b /= 2; 
        d *= 2; 
    } 
    printf("x=0x%08lX xor is 0x%08lX\n", x, 0x01234567ul ^ 0x87654321ul); 
} 


C:\Work\xor\Debug>xor 
x=0x86460646 xor is 0x86460646

Don't know if this is what you are looking for but it did work.

PS:  I kind of like that snip of code...

[niniyo]

OP - can you clarify whether integer operations are supported?  Like, 5 / 2 = 2?  Or, since it's purely mathematical, would that be 2.5?  If so, can we use the floor() function?

[OP_CHECKSIG]

Here's javascript code that works...

function xor32bit(a,b){
   var sum=0;
   var x,shift;
   var s32 = Math.pow(2,32);
   var s31 = Math.pow(2,31);

   for (n=0;n<32;n++){
      shift = Math.pow(2,n);
      // move current bits to b0 and add
      x= Math.floor(a/shift)+Math.floor(b/shift);
      // move to most significant bit to clear out left bits
      x*= s31;
      // mod to keep in 32 bits range
      x=x%s32;
      // divide to put back in right it position
      x=Math.floor(x/Math.pow(2,(31-n)));
      // add to sum
      sum+=x;
   }
   return sum;
}

console.log(xor32bit(0x12345678,0).toString(16));
console.log(xor32bit(0x12345678,0xffffffff).toString(16));

Equation is sum for n 0..31 (((a/2^n+b/2^n)x2^31)mod 2^32)/2^(31-n)

[Evil-Knievel]

This message was too old and has been purged

[niniyo]

OK here is my final submission which should be purely mathematical and doesn't require rounded integer arithmetic operations.  It uses a floor() function.

Code:

; note that the following two helper functions are mathematical expressions, and i'm just going to use them like macros to avoid repeating the same expression all the time
function mymod (value, modpow) =>
  ; returns the 32-bit result of value mod 2^modpow
  ((value * 2^(32-modpow) MOD 2^32) / 2^(32-modpow));

function clearbits (value, n) =>
  ; returns the 32-bit value with the lowest n bits cleared
  floor(value / 2^n) * 2^n;

; main function for calculating the result.  returns the 32-bit result of a bitwise-xor b.
function myxor (a, b) =>
  sum from n = 1 to 32:
    ; add the value of the nth bit of the xor result
    mymod(clearbits(mymod(a,n), n-1) + clearbits(mymod(a,n), n-1), n)

[BurtW]

Here's javascript code that works...

function xor32bit(a,b){
   var sum=0;
   var x,shift;
   var s32 = Math.pow(2,32);
   var s31 = Math.pow(2,31);

   for (n=0;n<32;n++){
      shift = Math.pow(2,n);
      // move current bits to b0 and add
      x= Math.floor(a/shift)+Math.floor(b/shift);
      // move to most significant bit to clear out left bits
      x*= s31;
      // mod to keep in 32 bits range
      x=x%s32;
      // divide to put back in right it position
      x=Math.floor(x/Math.pow(2,(31-n)));
      // add to sum
      sum+=x;
   }
   return sum;
}

console.log(xor32bit(0x12345678,0).toString(16));
console.log(xor32bit(0x12345678,0xffffffff).toString(16));

Equation is sum for n 0..31 (((a/2^n+b/2^n)x2^31)mod 2^32)/2^(31-n)

Basically what I did up above in my post but it looks like he is not looking for an algorithm...

[OP_CHECKSIG]

Expand the sum to long form?

Code:

x = ((((a+b)x2^31)mod 2^32)/2^(31))+((((a/2+b/2)x2^31)mod 2^32)/2^(30))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(29))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(28))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(27))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(26))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(25))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(24))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(23))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(22))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(21))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(20))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(19))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(18))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(17))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(16))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(15))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(14))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(13))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(12))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(11))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(10))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(9))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(8))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(7))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(6))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(5))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(4))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(3))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(2))+
((((a/(2^2)+b/(2^2))x2^31)mod 2^32)/2^(1))+((((a/(2^3)+b/(2^3))x2^31)mod 2^32)/2^(0))

[BurtW]

The above post is NOT correct but this one is, and it is just the unwinding of my loop in post #8 above so it is the same solution.

Code:

     x = (a/0x00000001 + b/0x00000001) * 0x80000000 / 0x80000000 + 
        (a/0x00000002 + b/0x00000002) * 0x80000000 / 0x40000000 + 
        (a/0x00000004 + b/0x00000004) * 0x80000000 / 0x20000000 + 
        (a/0x00000008 + b/0x00000008) * 0x80000000 / 0x10000000 + 
        (a/0x00000010 + b/0x00000010) * 0x80000000 / 0x08000000 + 
        (a/0x00000020 + b/0x00000020) * 0x80000000 / 0x04000000 + 
        (a/0x00000040 + b/0x00000040) * 0x80000000 / 0x02000000 + 
        (a/0x00000080 + b/0x00000080) * 0x80000000 / 0x01000000 + 
        (a/0x00000100 + b/0x00000100) * 0x80000000 / 0x00800000 + 
        (a/0x00000200 + b/0x00000200) * 0x80000000 / 0x00400000 + 
        (a/0x00000400 + b/0x00000400) * 0x80000000 / 0x00200000 + 
        (a/0x00000800 + b/0x00000800) * 0x80000000 / 0x00100000 + 
        (a/0x00001000 + b/0x00001000) * 0x80000000 / 0x00080000 + 
        (a/0x00002000 + b/0x00002000) * 0x80000000 / 0x00040000 + 
        (a/0x00004000 + b/0x00004000) * 0x80000000 / 0x00020000 + 
        (a/0x00008000 + b/0x00008000) * 0x80000000 / 0x00010000 + 
        (a/0x00010000 + b/0x00010000) * 0x80000000 / 0x00008000 + 
        (a/0x00020000 + b/0x00020000) * 0x80000000 / 0x00004000 + 
        (a/0x00040000 + b/0x00040000) * 0x80000000 / 0x00002000 + 
        (a/0x00080000 + b/0x00080000) * 0x80000000 / 0x00001000 + 
        (a/0x00100000 + b/0x00100000) * 0x80000000 / 0x00000800 + 
        (a/0x00200000 + b/0x00200000) * 0x80000000 / 0x00000400 + 
        (a/0x00400000 + b/0x00400000) * 0x80000000 / 0x00000200 + 
        (a/0x00800000 + b/0x00800000) * 0x80000000 / 0x00000100 + 
        (a/0x01000000 + b/0x01000000) * 0x80000000 / 0x00000080 + 
        (a/0x02000000 + b/0x02000000) * 0x80000000 / 0x00000040 + 
        (a/0x04000000 + b/0x04000000) * 0x80000000 / 0x00000020 + 
        (a/0x08000000 + b/0x08000000) * 0x80000000 / 0x00000010 + 
        (a/0x10000000 + b/0x10000000) * 0x80000000 / 0x00000008 + 
        (a/0x20000000 + b/0x20000000) * 0x80000000 / 0x00000004 + 
        (a/0x40000000 + b/0x40000000) * 0x80000000 / 0x00000002 + 
        (a/0x80000000 + b/0x80000000) * 0x80000000 / 0x00000001 ;

Tested and it works on C++.  You may need to add some masking and truncating operations in there - depending on exactly how the programming language you use works.  However, the basic idea is sound.

Did I win?

[gogodr]

uhm...I have a very simple solution here...

entry 1:
XOR:
f(x,y) = 0^(0^((1+x)mod(1+y)));

entry 2:
XOR:
f(x,y) = 0^(0^(x-y)); ,x>=y
f(x,y) = 0^(0^(y-x)); ,x<y


you know 0^0 == 1 , you can use that to convert logic into mathematics.
f(5,5) == 0
f(5,6) == 1
f(6,0) == 1
f(0,0) == 0

edit: I know 0^0 should be indeterminate but it is a convention.

[BurtW]

uhm...I have a very simple solution here...

entry 1:
XOR:
f(x,y) = 0^(0^((1+x)mod(1+y)));

entry 2:
XOR:
f(x,y) = 0^(0^(x-y)); ,x>=y
f(x,y) = 0^(0^(y-x)); ,x<y


you know 0^0 == 1 , you can use that to convert logic into mathematics.
f(5,5) == 0
f(5,6) == 1
f(6,0) == 1
f(0,0) == 0

He wants the bitwise XOR of the values:

XOR(5,5) = 0
XOR(5,6) = 3
XOR(6,0) = 6
XOR(0,0) = 0

So your formula does not give the correct results, however, mine does

[niniyo]

You may need to add some masking and truncating operations in there - depending on exactly how the programming language you use works.  However, the basic idea is sound.

Did I win?

No.  The whole point was that it has to be a purely mathematical solution.  Relying on a programming language to truncate values and handle overflows is not purely mathematical.  You're supposed to think in terms of mathematical operations, not machine operations.

[BurtW]

Here I added the one allowed mod operation.  Per this explaination of what is allowed:

That means, that if you create an overflow and you temporarily use more than 32 bits, you can strip it down to 32bit my using a "mod 2^32-1" operation 

The allowed mod operation is actually mod 2^32 not 2^32-1 as suggested in the OP - OP should be corrected.

This is pure integer math, not relying on the "machine" to do the truncation of the multiply.

As far as I can tell this single equation should satisfy the requirements of the puzzle.

Code:

     x = (((a/0x00000001 + b/0x00000001) * 0x80000000) % 0x100000000) / 0x80000000 + 
	(((a/0x00000002 + b/0x00000002) * 0x80000000) % 0x100000000) / 0x40000000 + 
	(((a/0x00000004 + b/0x00000004) * 0x80000000) % 0x100000000) / 0x20000000 + 
	(((a/0x00000008 + b/0x00000008) * 0x80000000) % 0x100000000) / 0x10000000 + 
	(((a/0x00000010 + b/0x00000010) * 0x80000000) % 0x100000000) / 0x08000000 + 
	(((a/0x00000020 + b/0x00000020) * 0x80000000) % 0x100000000) / 0x04000000 + 
	(((a/0x00000040 + b/0x00000040) * 0x80000000) % 0x100000000) / 0x02000000 + 
	(((a/0x00000080 + b/0x00000080) * 0x80000000) % 0x100000000) / 0x01000000 + 
	(((a/0x00000100 + b/0x00000100) * 0x80000000) % 0x100000000) / 0x00800000 + 
	(((a/0x00000200 + b/0x00000200) * 0x80000000) % 0x100000000) / 0x00400000 + 
	(((a/0x00000400 + b/0x00000400) * 0x80000000) % 0x100000000) / 0x00200000 + 
	(((a/0x00000800 + b/0x00000800) * 0x80000000) % 0x100000000) / 0x00100000 + 
	(((a/0x00001000 + b/0x00001000) * 0x80000000) % 0x100000000) / 0x00080000 + 
	(((a/0x00002000 + b/0x00002000) * 0x80000000) % 0x100000000) / 0x00040000 + 
	(((a/0x00004000 + b/0x00004000) * 0x80000000) % 0x100000000) / 0x00020000 + 
	(((a/0x00008000 + b/0x00008000) * 0x80000000) % 0x100000000) / 0x00010000 + 
	(((a/0x00010000 + b/0x00010000) * 0x80000000) % 0x100000000) / 0x00008000 + 
	(((a/0x00020000 + b/0x00020000) * 0x80000000) % 0x100000000) / 0x00004000 + 
	(((a/0x00040000 + b/0x00040000) * 0x80000000) % 0x100000000) / 0x00002000 + 
	(((a/0x00080000 + b/0x00080000) * 0x80000000) % 0x100000000) / 0x00001000 + 
	(((a/0x00100000 + b/0x00100000) * 0x80000000) % 0x100000000) / 0x00000800 + 
	(((a/0x00200000 + b/0x00200000) * 0x80000000) % 0x100000000) / 0x00000400 + 
	(((a/0x00400000 + b/0x00400000) * 0x80000000) % 0x100000000) / 0x00000200 + 
	(((a/0x00800000 + b/0x00800000) * 0x80000000) % 0x100000000) / 0x00000100 + 
	(((a/0x01000000 + b/0x01000000) * 0x80000000) % 0x100000000) / 0x00000080 + 
	(((a/0x02000000 + b/0x02000000) * 0x80000000) % 0x100000000) / 0x00000040 + 
	(((a/0x04000000 + b/0x04000000) * 0x80000000) % 0x100000000) / 0x00000020 + 
	(((a/0x08000000 + b/0x08000000) * 0x80000000) % 0x100000000) / 0x00000010 + 
	(((a/0x10000000 + b/0x10000000) * 0x80000000) % 0x100000000) / 0x00000008 + 
	(((a/0x20000000 + b/0x20000000) * 0x80000000) % 0x100000000) / 0x00000004 + 
	(((a/0x40000000 + b/0x40000000) * 0x80000000) % 0x100000000) / 0x00000002 + 
	(((a/0x80000000 + b/0x80000000) * 0x80000000) % 0x100000000) / 0x00000001 ;

[empoweoqwj]

Surely if the solution exists, you could just google it and paste in the solution? I'm guessing it can't be done ....