Topic: This message was too old and has been purged - page 4. (Read 6056 times)
This message was too old and has been purged
Most good calculators will accept hex numbers exactly as shown in my post. At any rate all the constants can be converted to decimal if needed. The formula is correct and satisfies the rules.
Did I win?
Did I win?
He basically wants to be able to put it into a calculator... Try doing 0x0001000 in a calculator and see what you get.
Surely if the solution exists, you could just google it and paste in the solution? I'm guessing it can't be done ....
Here I added the one allowed mod operation. Per this explaination of what is allowed:
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.
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 ;
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?
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.
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
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
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
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
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
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.
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
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.
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.
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?
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?
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))
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... 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)
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)
This message was too old and has been purged
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)
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)
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?
Code:
#include
#include
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...
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?
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?
This message was too old and has been purged
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?
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?
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
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.
Jump to: