wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Register Value Swap - Const. Time & No Extra M
        
(Message started by: StarmanDeluxe on Jun 2^nd, 2007, 1:10am)

Title: Register Value Swap - Const. Time & No Extra M
Post by StarmanDeluxe on Jun 2^nd, 2007, 1:10am

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

[hideb]
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
}
[/hideb]

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!

Title: Re: Register Value Swap - Const. Time & No Ext
Post by naveen on Jun 2^nd, 2007, 4:35am

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

Title: Re: Register Value Swap - Const. Time & No Ext
Post by towr on Jun 2^nd, 2007, 9:21am

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

Title: Re: Register Value Swap - Const. Time & No Ext
Post by StarmanDeluxe on Jun 3^rd, 2007, 3:33pm

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?

Title: Re: Register Value Swap - Const. Time & No Ext
Post by towr on Jun 3^rd, 2007, 11:49pm

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.

Title: Re: Register Value Swap - Const. Time & No Ext
Post by Grimbal on Jun 4^th, 2007, 2:09am

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.

Title: Re: Register Value Swap - Const. Time & No Ext
Post by krishnav on Jan 12^th, 2012, 9:01am

XOR always works, even when the numbers are big enough to cause overflows when they are added

Title: Re: Register Value Swap - Const. Time & No Ext
Post by Grimbal on Jan 12^th, 2012, 9:13am

add/sub also works, if you just ignore the overflow. n-bit integers just compute modulo 2^n.

Title: Re: Register Value Swap - Const. Time & No Ext
Post by birbal on Jan 14^th, 2012, 10:02am

x = x xor y
y = x xor y
x = x xor y

Title: Re: Register Value Swap - Const. Time & No Ext
Post by Stefan Kneifel on Jan 27^th, 2012, 12:45pm

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.