On Thursday 30 November 2006 11:00, Bill Long wrote:
> If you don't have access to such systems, or require more portable
> code, try looking at the algorithms at www.hackersdelight.org for
> generalized bit compression and extraction, and then specialize the code
> for your case.
Thanks to all that responded. I found a paper that proposes smart ways to do
this, including ones free of tables and almost as fast:
http://www.cs.indiana.edu/~dswise/Arcee/castingDilated-comb.pdf
Very cute. for example, 3-dilation (adding 2 zeros between each bit) is done
with the C code:
inline u_int dilate_3(u_short t) { u_int r = t; r = (r * 0x10001) &
0xFF0000FF; r = (r * 0x00101) & 0x0F00F00F; r = (r * 0x00011) & 0xB30B30B3; r
= (r * 0x00005) & 0x49249249; return(r); }
The paper also has the table lookup version that breaks things into bytes
first.
Aleks
--
Aleksandar Donev, Ph.D.
Lawrence Postdoctoral Fellow @ LLNL
High Performance Computational Materials Science and Chemistry
E-mail: [log in to unmask]
Phone: (925) 424-6816 Fax: (925) 423-0785
Address: P.O.Box 808, L-367, Livermore, CA 94551-9900
Web: http://cherrypit.princeton.edu/donev
|