Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!rpi!image.soe.clarkson.edu!news
From: gld2@clutx.clarkson.edu (E.W.D, ,0,0)
Newsgroups: comp.lang.c
Subject: Re: How to reverse bits...
Message-ID: <1990Aug14.124259.13475@sun.soe.clarkson.edu>
Date: 14 Aug 90 12:42:59 GMT
References: <487@demott.COM>
Sender: news@sun.soe.clarkson.edu
Reply-To: gld2@clutx.clarkson.edu
Distribution: usa
Organization: Clarkson University, Potsdam, NY
Lines: 36

From article <487@demott.COM>, by kdq@demott.COM (Kevin D. Quitt):
> In article <1990Aug13.185757.3236@sti.fi> ttl@sti.fi (Timo Lehtinen) writes:
>>This might be trivial, but here goes...
>>What's the most optimal way to reverse the bits in an unsigned char,
>>i.e. change from MSB to LSB ordering ?
>>
>     If by optimal, you mean fastest with the least code, try a char[256]
> array with the bits already reversed.  You just look 'em up.  (It may be
> gross, but the table+code is often smaller than the conversion code). 


Didn't this go around a while back?

Having actually tried tables we found that 
the best technique we found was to swap half
words, then half half words, ... down to 
adjacent bits (at least on VAX, Sun 3, and a 
few others).  This resulted in the most dramatic
cooling of one of the hottest hot spots I've seen.

long int n;                       /* the number */
long int numberofbitstostartwith; /* we're interested in this number of bits */
long int revn;                    /* the reversed number */

revn = n << ((sizeof (n) * 8) - numberofbitstostartwith);
revn = (0x0000FFFF & (revn >> 16)) | (0xFFFF0000 & (revn << 16));
revn = (0x00FF00FF & (revn >>  8)) | (0xFF00FF00 & (revn <<  8));
revn = (0x0F0F0F0F & (revn >>  4)) | (0xF0F0F0F0 & (revn <<  4));
revn = (0x33333333 & (revn >>  2)) | (0xCCCCCCCC & (revn <<  2));
revn = (0x55555555 & (revn >>  1)) | (0xAAAAAAAA & (revn <<  1));
 

Eliot W. Dudley                       edudley@rodan.acs.syr.edu
RD 1 Box 66
Cato, New York 13033                  315 437 0215