Most efficient way to manipulate bits
Harry Muscle
bit byte (ie: 01000000 becomes 00000010). Currently I'm doing this by AND
and OR to figure out if a bit is set and to set the corresponding bit ...
However, my problem is that this seems to create quite a lot of code ... and
I'm limited in code space (programming for a microcontroller ... Atmel
ATMega103).
I'm writing all of this in C (with the GNU-GCC compiler).
Is there any better way to do what I'm trying to accomplish above? Or is
using AND and OR pretty much my only way?
Thanks for the help,
Harry
Ben Pfaff
> I'm working on a function whose sole purpose is to reverse the bits in an 8
> bit byte (ie: 01000000 becomes 00000010). Currently I'm doing this by AND
> and OR to figure out if a bit is set and to set the corresponding bit ...
From the fortune cookie file:
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
-- C code which reverses the bits in a word.
Jos A. Horsmeier
news:3SHo8.23160$R8.19...@carnaval.risq.qc.ca...
Two difference approaches come to mind:
typedef unsigned char uc;
uc byterev(uc b) {
uc r= 0, i;
for (i= 8; i--; b>>= 1)
r= (r<<1)|(b&1);
return r;
}
or:
typedef unsigned char uc;
uc revtab[] = {
0x00, 0x80, 0x40, 0xc0 /* etc. */
/* revtab[b] == byterev(b) */
}
uc byterev(uc b) { return revtab[b]; }
kind regards,
Jos aka j...@gen.nl
Default User
Here's one out of my utilities file:
unsigned char ReverseBits (unsigned char b)
{
unsigned char c;
c = ((b >> 1) & 0x55) | ((b << 1) & 0xaa);
c |= ((b >> 2) & 0x33) | ((b << 2) & 0xcc);
c |= ((b >> 4) & 0x0f) | ((b << 4) & 0xf0);
return c;
}
Another way that is reasonable for eight-bit reversals is to use a
lookup table.
#define REVERSEBITS(b) (BitReverseTable[b])
unsigned char BitReverseTable[256] =
{
0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};
Brian Rodenborn
CBFalconer
Untested, written on the fly:
int rev8bits(int in)
{
int out, i;
for (out = i = 0; i < 8; i++) {
out <<= 1;
if (in & 1) out++;
in >>= 1;
}
return out & 0xff;
} /* rev8bits */
--
Chuck F (cbfal...@yahoo.com) (cbfal...@XXXXworldnet.att.net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
baz
"Harry Muscle" <harry.DOT.muscle@AT@usa.DOT.net> wrote in message
news:3SHo8.23160$R8.19...@carnaval.risq.qc.ca...
have a look at it's instruction set. it may have one for rotating bits. for
an x86 they are RCL / RCR / ROL / ROR
baz
Daniel Fox
news:JvNo8.24398$uR5....@newsfeeds.bigpond.com:
> "Harry Muscle" <harry.DOT.muscle@AT@usa.DOT.net> wrote in message
> news:3SHo8.23160$R8.19...@carnaval.risq.qc.ca...
>> I'm working on a function whose sole purpose is to reverse the bits
>> in an 8 bit byte (ie: 01000000 becomes 00000010). Currently I'm doing
[snip]
> have a look at it's instruction set. it may have one for rotating
> bits. for an x86 they are RCL / RCR / ROL / ROR
Rotating is not reversing, and secondly, why are you recommending
assembly language on a C newsgroup, when C can do the job just fine?
-Daniel
Al Dunbar
"Daniel Fox" <danielfox200...@hotmail.com> wrote in message
news:Xns91E01BADC43EC...@65.82.44.7...
> "baz" <hotf...@bigpond.com> wrote in
> news:JvNo8.24398$uR5....@newsfeeds.bigpond.com:
>
> > "Harry Muscle" <harry.DOT.muscle@AT@usa.DOT.net> wrote in message
> > news:3SHo8.23160$R8.19...@carnaval.risq.qc.ca...
>
> >> I'm working on a function whose sole purpose is to reverse the bits
> >> in an 8 bit byte (ie: 01000000 becomes 00000010). Currently I'm doing
>
> [snip]
>
> > have a look at it's instruction set. it may have one for rotating
> > bits. for an x86 they are RCL / RCR / ROL / ROR
>
> Rotating is not reversing,
No, but one can ROL the bits out of one byte, and ROR them into another.
/Al
Michael Hinz
> "baz" <hotf...@bigpond.com> wrote in
> news:JvNo8.24398$uR5....@newsfeeds.bigpond.com:
> > have a look at it's instruction set. it may have one for rotating
> > bits. for an x86 they are RCL / RCR / ROL / ROR
>
> Rotating is not reversing, and secondly, why are you recommending
> assembly language on a C newsgroup, when C can do the job just fine?
Rotating is one way of solving the problem at hand and not everybody
read this in comp.lang.c (yeah, sure, no reason to not trim the newsgroups,
or at least to not set followups).
Nevertheless, resorting to assembly language *is* a step backwards. On the
other hand, *only* rotates are a more expensive operation (n rotates for a
n-bit word) than the ANDing solution (10 rotates, 10 ANDs and 5 ORs for a
32-bit word) also mentioned in this thread.
Set Followup-To to comp.programming
Michael
--
> >I see. ruby:perl :: pascal:C .
> Be fair. PASCAL's not *that* bad.
I am being fair. Perl's not that good.
-- Peter da Silva and Simon Cozens
Kevin D. Quitt
you can use:
unsigned char byteReverse( unsigned char c )
{
static unsigned char hi[] =
{
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0
};
static unsigned char lo[] =
{
0x00, 0x08, 0x04, 0x0C, 0x02, 0x0A, 0x06, 0x0E,
0x01, 0x09, 0x05, 0x0D, 0x03, 0x0B, 0x07, 0x0F
};
return hi[ c & 0xF ] | lo[ (c >> 4) & 0xF ];
}
You can also eliminate the hi array by adding a shift. This saves about
12 bytes and adds 4 instruction times (probably). This assumes the
compiler doesn't promote to integer and call a library or do 16-bit ops.
return (lo[ c & 0xF ] << 4) | lo[ (c >> 4) & 0xF ];
You need to look at the assembly-language output to be sure. If this is a
speed-critical routine and the compiler doesn't generate close-to-optimal
code for your processor, I would put the C source in a comment block and
put the assembly in-line.
--
#include <standard.disclaimer>
_
Kevin D Quitt USA 91351-4454 96.37% of all statistics are made up
Per the FCA, this email address may not be added to any commercial mail list
Ben Pfaff
> If speed is more important than size, but a 256 byte table is too large,
> you can use:
>
> unsigned char byteReverse( unsigned char c )
> {
> static unsigned char hi[] =
> {
> 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
> 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0
> };
> static unsigned char lo[] =
> {
> 0x00, 0x08, 0x04, 0x0C, 0x02, 0x0A, 0x06, 0x0E,
> 0x01, 0x09, 0x05, 0x0D, 0x03, 0x0B, 0x07, 0x0F
> };
>
> return hi[ c & 0xF ] | lo[ (c >> 4) & 0xF ];
It seems to me that
return hi[c & 0xf] | lo[c >> 4];
i.e., removing the second & 0xf, is equivalent, assuming an 8-bit
unsigned char.
> }
--
"Some people *are* arrogant, and others read the FAQ."
--Chris Dollin
Kevin D. Quitt
>> return hi[ c & 0xF ] | lo[ (c >> 4) & 0xF ];
>
>It seems to me that
> return hi[c & 0xf] | lo[c >> 4];
>i.e., removing the second & 0xf, is equivalent, assuming an 8-bit
>unsigned char.
It certainly should be, but I'm a paranoid sort who's had to fight too
many compiler bugs. I figure if the compiler is smart enough to do it
right, it'll likely optimize away the mask. The last time I did this, the
compiler would optimize away the mask and do it right if the mask was
there, but would do an arithmetic shift if it wasn't.
George Kinney
"Harry Muscle" <harry.DOT.muscle@AT@usa.DOT.net> wrote in message
news:3SHo8.23160$R8.19...@carnaval.risq.qc.ca...
Ben Pfaff
> Why not just XOR against 11111111? That'll flip the bits.
But it won't do what the OP is asking for. BTW please don't
top-post like that.
> "Harry Muscle" <harry.DOT.muscle@AT@usa.DOT.net> wrote in message
> news:3SHo8.23160$R8.19...@carnaval.risq.qc.ca...
> > I'm working on a function whose sole purpose is to reverse the bits in an
> 8
> > bit byte (ie: 01000000 becomes 00000010). [...]
Bertrand Mollinier Toublet
I guess it depends on what you call a lot of code, but,
representing your 8 bits as an unsigned char, something like :
unsigned char reverse(unsigned char a)
{
return ((a & 0x80) >> 7)
| ((a & 0x40) >> 5)
| ((a & 0x20) >> 3)
| ((a & 0x10) >> 1)
| ((a & 0x08) << 1)
| ((a & 0x04) << 3)
| ((a & 0x02) << 5)
| ((a & 0x01) << 7);
}
seems satisfactorily to me.
Of course, you might as well want to try and consider some
specific function available on your chip, possibly implementable in
assembly. However, this is obviously off-topic on this NG.
--
bmt