Author |
Topic: XOR with Arithmetic Ops (Read 1912 times) |
|
R
Senior Riddler
Addicted!!!
Gender: 
Posts: 502
|
 |
XOR with Arithmetic Ops
« on: Apr 28th, 2010, 12:03am » |
 Quote  Modify
|
How will you implement XOR operation on integers using only arithmetic operators in a certain language which does not support bitwise operations?
|
|
 IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: XOR with Arithmetic Ops
« Reply #1 on: Apr 28th, 2010, 12:15am » |
Quote Modify
|
One way to do it would be:
Code:function xor(x,y)
{
s = 2;
r = 0;
while (s <= x && s <= y)
{
r += (x + y) % s;
x -= x%s;
y -= y%s;
s *= 2;
}
return r;
} |
|
|
| « Last Edit: Apr 28th, 2010, 12:16am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: XOR with Arithmetic Ops
« Reply #2 on: Apr 28th, 2010, 12:23am » |
Quote Modify
|
Can you optimize it more? Divide and modulus are very expensive operations for Big Integers.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: XOR with Arithmetic Ops
« Reply #3 on: Apr 28th, 2010, 12:49am » |
Quote Modify
|
I suppose we can start from the other end.
Code:function xor(x,y)
{
stack.push(1);
while (x > stack.top() && y > stack.top())
stack.push(stack.top() + stack.top());
r=0;
while (!stack.isempty() )
{
if (x >= stack.top())
{
x -= stack.top();
if (y >= stack.top())
y -= stack.top();
else
r += stack.top();
}
else if (y >= stack.top())
{
y -= stack.top();
r += stack.top();
}
stack.pop();
}
return r;
} |
|
|
| « Last Edit: Apr 28th, 2010, 12:52am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print