Reverse a byte

J

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

Eric Sosman

John said:
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];
 
G

Grumble

John said:
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.
 
I

Ivan Vecerina

| 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
 
T

Thomas Matthews

John said:
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
 
D

Dan Pop

In said:
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
 
J

John Deuf

Thanks all, I got what I need here.

This forum is really effective !


Eric Sosman said:
John said:
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];
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top