Reverse a byte

[John Deuf]

Does somebody has a better algorithm than mine to reverse a byte
(i.e. bit 0 becomes 7, bit 1 becomes 6 ...)

unsigned char u=0, c = TESTVALUE;
int i;

for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| ((c & (1 << 7-i)) >> (7-2*i));

I need something quick. Thx.

[Eric Sosman]

John Deuf wrote:

Does somebody has a better algorithm than mine to reverse a byte
(i.e. bit 0 becomes 7, bit 1 becomes 6 ...)

unsigned char u=0, c = TESTVALUE;
int i;

for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| ((c & (1 << 7-i)) >> (7-2*i));

#include <limits.h>
#if UCHAR_MAX != 0xFF
#error "Re-build table for non-8-bit byte!"
#endif
...
static const unsigned char reversed[] = {
0x00, 0x80, 0x40, 0xC0, ..., 0xEF, oxFF };
u = reversed[c];

--
Er*********@sun.com

[Grumble]

John Deuf wrote:

Does somebody has a better algorithm than mine to reverse a byte
(i.e. bit 0 becomes 7, bit 1 becomes 6 ...)

unsigned char u=0, c = TESTVALUE;
int i;

for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| ((c & (1 << 7-i)) >> (7-2*i));

If your bytes are only 8-bits wide, then I believe a lookup table
will be the fastest solution (as Eric pointed out).

If your bytes are wider, it might not be practical.

[Ivan Vecerina]

"John Deuf" <go****@spongers.com> wrote in message
news:97************************@posting.google.com ...
| Does somebody has a better algorithm than mine to reverse a byte
| (i.e. bit 0 becomes 7, bit 1 becomes 6 ...)
|
| unsigned char u=0, c = TESTVALUE;
| int i;
|
| for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| | ((c & (1 << 7-i)) >> (7-2*i));

As an alternative to a lookup, it is possible to perform
the operation in O(lg(N)) instead of O(N):

For an 8-bit byte stored in c:

c = ((c>>1)&0x55)|((c<<1)&0xAA);
c = ((c>>2)&0x33)|((c<<2)&0xCC);
c = (c>>4) | (c<<4) ; //NB: code not tested

This is obviously easy to scale up to 16/32/64 bytes and,
in some situations, could be faster than a lookup...
Regards,
Ivan
--
http://ivan.vecerina.com

[Thomas Matthews]

John Deuf wrote:

Does somebody has a better algorithm than mine to reverse a byte
(i.e. bit 0 becomes 7, bit 1 becomes 6 ...)

unsigned char u=0, c = TESTVALUE;
int i;

for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| ((c & (1 << 7-i)) >> (7-2*i));

I need something quick. Thx.

A better solution may be to use assembly language.
Use the rotation instructions. Rotate the original
right into carry, then rotate carry into the result.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

[Dan Pop]

In <bo**********@news-rocq.inria.fr> Grumble <in*****@kma.eu.org> writes:

John Deuf wrote:

Does somebody has a better algorithm than mine to reverse a byte
(i.e. bit 0 becomes 7, bit 1 becomes 6 ...)

unsigned char u=0, c = TESTVALUE;
int i;

for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| ((c & (1 << 7-i)) >> (7-2*i));

If your bytes are only 8-bits wide, then I believe a lookup table
will be the fastest solution (as Eric pointed out).

If your bytes are wider, it might not be practical.

For larger values of CHAR_BIT that are powers of two, an adaptation of
the following algorithm is much better than the bit by bit approach:

c = (c & 0x0F) << 4 | (c & 0xF0) >> 4;
c = (c & 0x33) << 2 | (c & 0xCC) >> 2;
c = (c & 0x55) << 1 | (c & 0xAA) >> 1;

For a 16-bit byte you only need one more "iteration", which is left as
an exercise to the reader.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[John Deuf]

Thanks all, I got what I need here.

This forum is really effective !
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...

John Deuf wrote:

Does somebody has a better algorithm than mine to reverse a byte
(i.e. bit 0 becomes 7, bit 1 becomes 6 ...)

unsigned char u=0, c = TESTVALUE;
int i;

for (i=0 ; i<4 ; i++) u |= ((c & (1 << i)) << (7-2*i))
| ((c & (1 << 7-i)) >> (7-2*i));

#include <limits.h>
#if UCHAR_MAX != 0xFF
#error "Re-build table for non-8-bit byte!"
#endif
...
static const unsigned char reversed[] = {
0x00, 0x80, 0x40, 0xC0, ..., 0xEF, oxFF };
u = reversed[c];