Author: Matt Taylor
Date: 22:54:34 01/23/03
Go up one level in this thread
On January 21, 2003 at 17:16:46, Dann Corbit wrote:
>On January 21, 2003 at 17:14:08, Dann Corbit wrote:
>
>>http://www.cs.ucsd.edu/users/carter/Papers/focspdf.pdf
>
>Kang Su Gatlin's implementation of the COBRA bit reversal algorithm:
>http://www.cs.ucsd.edu/~kgatlin/cobra.tar.gz
Ok, I did have a thorough look at COBRA, and it seems that it's really optimized
for -huge- bit sequences. By huge, I'm talking about multiple KBs and upward.
We're dealing with 8 bytes.
COBRA's handling of a word-sized flip is the following function:
int bitrev(int x, int lgn)
{
int i, t, value;
value = 0;
for(i = lgn-1; i >= 0; i--)
{
t = 1 & x;
value = (value | (t << i));
x = x >> 1;
}
return(value);
}
Worst-case runtime: has to iterate a number of times equal to the number of bits
in int. The logarithmic time version is -much- better.
-Matt
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.