Author |
Topic: Register Value Swap - Const. Time & No Extra M (Read 3604 times) |
|
StarmanDeluxe
Newbie
Gender: 
Posts: 2
|
 |
Register Value Swap - Const. Time & No Extra M
« on: Jun 2nd, 2007, 1:10am » |
 Quote  Modify
|
Hello all, this is my first post & topic, so be nice. =)
This was the riddle:
In constant time, without using any extra memory, exchange the values of two equally sized variables (e.g. 32 Bit Ints, but infinitely long also works, giving it a more theoretical touch).
| hidden: |
Using bitwise exclusive OR (XOR), this problem can be solved quite easily. For those of you who don't know, this is the truth table for XOR:
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
An interesting property of XOR is that if you XOR value1 by value2, then take that and XOR it by value2, you get value1.
For example:
val1 = 1001
val2 = 0101 ^
-----------------
(new)= 1100
val2 = 0101 ^
-----------------
val1 = 1001
Here is how the swapping works, with any arbitrary values of equal size:
a=0xF;
b=0xA;
0000 1111 = a
^0000 1010 = b
---------------------
0000 0101 = a ^ b
0000 1010 = b
^0000 0101 = a
---------------------
0000 1111 = b (now a's original value)
0000 0101 = a
^0000 1111 = b
---------------------
0000 1010 = a (now b's original value)
Simple implementation in C:
#include "stdio.h"
void main(void){
int a, b;
a=rand( ); // Assign arbitrary value
b=rand( ); // Ditto
printf("a=%i\nb=%i\n", a, b); // Print original values
a ^= b;
b ^= a;
a ^= b;
printf("a=%i\nb=%i\n", a, b); // Print switched values
}
|
I'm relatively new to computer science (just a teenager), but think constant time means that time needed to compute this doesn't vary with the size of the input, in otherwords, O(1). Also, this method doesn't use any temp variable, so there is less memory usage. I'm definitely keeping this in my bag of tricks!
|
|
 IP Logged |
|
|
|
naveen
Newbie
Posts: 3
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #1 on: Jun 2nd, 2007, 4:35am » |
Quote Modify
|
We can also do the required with some basic arithmetic operation as below:
initially : a , b two variables
do following arithmetic operations and assignments:
a = (a+b) //
b = a- 2b // b = a-b now
a = (a-b) /2 // a = b
b = a + b // b=a
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #2 on: Jun 2nd, 2007, 9:21am » |
Quote Modify
|
The last solution can be shorter
//pre: a=A, b=B
a=a+b // a=A+B
b=a-b // b=A
a=a-b // a=B
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
StarmanDeluxe
Newbie
Gender:
Posts: 2
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #3 on: Jun 3rd, 2007, 3:33pm » |
Quote Modify
|
Just curious, which one is faster? I've been told that bitwise operations are faster than arithmetic operations, but I'm not quite sure. I tried testing it on my computer, and the results were about the same. Since processors are better (faster) now, does it make a big difference?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #4 on: Jun 3rd, 2007, 11:49pm » |
Quote Modify
|
I don't really know which is faster. A processing unit dedicated to XORing can be faster than one dedicated to addition/subtraction; but such a distinction is never the case. Forcing operations into CPU cycles may well result in them taking equally long.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #5 on: Jun 4th, 2007, 2:09am » |
Quote Modify
|
From an electronic point of view, an XOR is simpler and faster than an addition or subtraction. But these are so fast anyway that they execute in a single CPU cycle, so it shouldn't make a difference.
By the way, I wonder if some compilers are smart enough to optimize this operation into a swap.
|
|
IP Logged |
|
|
|
krishnav
Newbie
Posts: 12
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #6 on: Jan 12th, 2012, 9:01am » |
Quote Modify
|
XOR always works, even when the numbers are big enough to cause overflows when they are added
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #7 on: Jan 12th, 2012, 9:13am » |
Quote Modify
|
add/sub also works, if you just ignore the overflow. n-bit integers just compute modulo 2^n.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #8 on: Jan 14th, 2012, 10:02am » |
Quote Modify
|
x = x xor y
y = x xor y
x = x xor y
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Stefan Kneifel
Newbie
Gender:
Posts: 25
|
|
Re: Register Value Swap - Const. Time & No Ext
« Reply #9 on: Jan 27th, 2012, 12:45pm » |
Quote Modify
|
From a processor's point of view, this "trick" probably only enlarges your code, and does not save any space.
A compiler (on a 64 bit Intel/AMD processor, with optimizations) encodes this sequence probably as follows:
mov rax,[y]
xor [x],rax
mov rax,[x]
xor [y],rax
mov rax,[y]
xor [x],rax
There is no instruction XOR'ing two memory locations directly, you have always to use a register.
A conventional approach using a "register" class temporary variable, however, should encode to a shorter code:
register unsigned long t = x;
x = y;
y = t;
will be translated to:
mov rdx,[x]
mov rax,[y]
mov [x],rax
mov [y],rdx
which is two machine instructions shorter, and doesn't need any extra space in memory.
|
| « Last Edit: Jan 27th, 2012, 12:52pm by Stefan Kneifel » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print