reverse byte

[Zygmunt Krynicki]

The easiest, clearest and most efficient way is just to use a 256-entry
lookup table.

Forgive me for being architecture specific but intel chips have ror and rol
(roll bits right / left) instructions don't they? If the target processor
has similar instructions that would be far more effictient than any lookup
table or bit manipulation presented already.

Z.

 

[Alex]

Hi,
I am trying to reverse a byte eg.
11010000 should look like
00001011

Plz note, it is not a homework problem and I do not need the c code
for it.
Just give me an idea how should I proceed about it.

I know basic bit manipulation , shifting left, right and have done
simple problems like counting 1's etc but this one doesnt seem to
click to me.

This should do it:

#include <stdio.h>
#include <limits.h>

void display_binary(unsigned char val)
{
int i;

for(i = CHAR_BIT - 1; i >= 0; i--)
printf("%d", (val >> i) & 0x01);

printf("\n");
}

int main(void)
{
unsigned char input = 0xD0;
unsigned char output = 0;
unsigned char cur;
int i;

printf("Before: ");
display_binary(input);

for(i = 0; i < CHAR_BIT; i++)
{
cur = (input >> i) & 0x01;
output |= (cur << CHAR_BIT - i - 1);
}

printf("After: ");
display_binary(output);

return 0;
}

Alex

 

[Roger Willcocks]

you?

How's this? (note it only goes forward - the reverse one is nearly the

same)

ummm, isn't the reverse table exactly the same?

 

[Roger Willcocks]

Forgive me for being architecture specific but intel chips have ror and rol
(roll bits right / left) instructions don't they? If the target processor
has similar instructions that would be far more effictient than any lookup
table or bit manipulation presented already.

Z.

If we wanted to rotate bits, yes; but the question was how to reverse
bits...

 

[Kevin Easton]

On the Texas Instruments 2812 that I am writing code for today, it
would require 65,536 entries, because CHAR_BIT is 16, so that's how
many bits a byte has.

On the Analog Devices SHARC I coded for a few years ago, that would
have required a 4GB x 32 bit table, since all the integer types were
32 bits wide.

But I agree, except in very tight memory situations, a look up table
is by far the fastest if CHAR_BIT is 8.

I think the OPs example made it clear that he wanted to reverse an 8 bit
value (due to the zero padding stopping at the 8th bit), rather than
reverse an arbitrary char value.

- Kevin.

 

[Kevin Easton]

Forgive me for being architecture specific but intel chips have ror and rol
(roll bits right / left) instructions don't they? If the target processor
has similar instructions that would be far more effictient than any lookup
table or bit manipulation presented already.

I don't see how rotate instructions help you implement the requested
transformation.

- Kevin.

 

[CBFalconer]

Shudder

OK
unsigned i;
unsigned j;
Better?

Nope. What if UCHAR_MAX == UINT_MAX.

 

[CBFalconer]

If we wanted to rotate bits, yes; but the question was how to
reverse bits...

You are allowed to rotate bits left into the carry, and then right
from the carry into the destination. However no such operations
are built into C.

 

[Mac]

int revb(int n) {
n = ((n >> 1) & 0x55) | ((n << 1) & 0xaa);
n = ((n >> 2) & 0x33) | ((n << 2) & 0xcc);
n = ((n >> 4) & 0x0f) | ((n << 4) & 0xf0);
return n;
}

click?

Clicks for me.

This is really a beautiful solution. The flow of bits from one stage to
the next is just like the flow of data through the classic radix 2 FFT,
which, interestingly enough, is where the problem of reversing bits seems
to be used most of the time.

Too bad it only works when the number of bits to reverse is a power of two.

Mac
--

 

[Christopher Benson-Manica]

ummm, isn't the reverse table exactly the same?

Well, if the idea is to reverse bytes (and generate a lookup table), table[1]
should be 11111110 (assuming 8-bit characters), right?

 

[Zygmunt Krynicki]

If we wanted to rotate bits, yes; but the question was how to reverse
bits...

Ah... REVERSE, sorry I was working late yesterday. Of course that renders
bit rotation usless.

Z.

 

[pete]

Mac wrote:

Too bad it only works when
the number of bits to reverse is a power of two.

/* BEGIN rev_byte.c */

#include <stdio.h>

int main(void)
{
unsigned char byte, revbyte, hi_mask, lo_mask;

byte = 0;
do {
--byte;
revbyte = byte;
hi_mask = ((unsigned char)-1 >> 1) + 1;
lo_mask = 1;
do {
if (!(revbyte & hi_mask) != !(revbyte & lo_mask)) {
revbyte ^= hi_mask | lo_mask;
}
hi_mask >>= 1;
lo_mask <<= 1;
} while (hi_mask > lo_mask);
printf(" byte = %3u, revbyte = %3u\n",
(unsigned)byte, (unsigned)revbyte);
} while (byte);
return 0;
}

/* END rev_byte.c */

 

[Tauno Voipio]

ummm, isn't the reverse table exactly the same?

Well, if the idea is to reverse bytes (and generate a lookup table), table[1]
should be 11111110 (assuming 8-bit characters), right?

This is bit-inversion (C operator ~), not reverse.

HTH

Tauno Voipio
tauno voipio @ iki fi

 

[Jirka Klaue]

Do what I did, google for one, copy it into your code, presto.

No, thanks.
BTW: You snipped the link to the look-up table and 'google' is not a synonym
for 'web search', even if most users assume this. ;-)

Jirka

 

[Christopher Benson-Manica]

This is bit-inversion (C operator ~), not reverse.

So it is. (my little program still gets cool points though, right??)

 

[Default User]

No, thanks.

Your call, but don't bitch about it.

BTW: You snipped the link to the look-up table

I did even better, posted my results. Why should I post a link?

and 'google' is not a synonym
for 'web search', even if most users assume this. ;-)

I don't recommend any other search engine.


Brian Rodenborn

 

[pete]

This seems to be a good solution,
although as far as I understand it,
it doesn't really expand the solution space
of the previous example that much.
Practically speaking, the possible number of bits for unsigned char
is 8, 16, 24, 32, 64. All of those are powers of two except 24, so the
power of two solution will work.
Your solution, if I understand correctly,
will also work on the 24-bit unsigned char.

When I had to solve this problem,
I wanted to support any number of bits.

That's the only kind of code that's really on topic here.

The loop only executes (CHAR_BIT / 2) times.
The bits which match their opposites, don't get overwritten.

 

[Mac]

/* BEGIN rev_byte.c */

#include <stdio.h>

int main(void)
{
unsigned char byte, revbyte, hi_mask, lo_mask;

byte = 0;
do {
--byte;
revbyte = byte;
hi_mask = ((unsigned char)-1 >> 1) + 1;
lo_mask = 1;
do {
if (!(revbyte & hi_mask) != !(revbyte & lo_mask)) {
revbyte ^= hi_mask | lo_mask;
}
hi_mask >>= 1;
lo_mask <<= 1;
} while (hi_mask > lo_mask);
printf(" byte = %3u, revbyte = %3u\n",
(unsigned)byte, (unsigned)revbyte);
} while (byte);
return 0;
}

/* END rev_byte.c */

This seems to be a good solution, although as far as I understand it, it
doesn't really expand the solution space of the previous example that
much. Practically speaking, the possible number of bits for unsigned char
is 8, 16, 24, 32, 64. All of those are powers of two except 24, so the
power of two solution will work. Your solution, if I understand correctly,
will also work on the 24-bit unsigned char.

When I had to solve this problem, I wanted to support any number of bits.
Since I was doing this to support a naive radix 2 FFT, I didn't worry
about size. I figured that if the machine could handle the data it was
using for the FFT, it could handle the LUT, since they would be the same
size.

You inspired me to go back and look at what I did. It looks like I
specified the number of bits, and then copied one bit at a time into the
appropriate place in the LUT.

Here it is. I am the sole author of the following code for copyright
purposes, and I hereby formally release it into the public domain. (I
didn't check to see if it violates any software patents. ;-))

int *build_bitrev_lut(unsigned int num_pts, int num_bits)
/**********************************************
allocates array of size num_pts, and creates a
"bitrev" (bit reversing) look-up table (lut)
in the array. Once this is done, bit reversal
can be effected simply by using array indexing.
e.g., temp = data; data=data[bitrev];
data[bitrev]=temp;
**********************************************/
{
int i, j, *bitrev;
bitrev = calloc(num_pts, sizeof *bitrev);
if (NULL == bitrev)
return NULL;
for (i=0; i<num_pts; i++)
for (j=0; j<num_bits; j++)
bitrev = (bitrev << 1) + ((i >> j) & 1);
return bitrev;
}

Mac
--

 

[Mac]

On Sun, 28 Sep 2003 06:02:32 +0000, pete wrote:

[snip]

That's the only kind of code that's really on topic here.

I'm not sure what you mean.

The loop only executes (CHAR_BIT / 2) times.
The bits which match their opposites, don't get overwritten.

Yeah, that's what I thought. I guess my point is that for an fft of, say,
32 points, you need to swap bit 0 with bit 4, and bit 1 with bit 3. Bit 2
doesn't need to move. In this situation, my code would create a lookup
table with just 32 entries, so there is no need to worry about numbers
bigger than 31.

The cool thing about the algorithm in the post before yours is that it
actually could be made into a loop that executes log base 2 of the number
of bits times. Since the OP had the number of bits fixed at 8 (implied)
the loop was unrolled to 3 iterations.

Anyway, your code is more optimised than mine since it only loops through
number of bits/2, and mine loops through all the bits.

Mac
--

 

[Steve Zimmerman]

Hi,
I am trying to reverse a byte eg.
11010000 should look like
00001011

Plz note, it is not a homework problem and I do not need the c code
for it.
Just give me an idea how should I proceed about it.

I know basic bit manipulation , shifting left, right and have done
simple problems like counting 1's etc but this one doesnt seem to
click to me.

Thanks.
Kapil

Thank you for your post, Kapil.

I have a working program that might do what you want,
and I'll give it to you if you want.

Here is how I do it.

I ask the user to enter some digits.
I use a function called "read_line" to store the digits.
I use a function called "reverse" to reverse the digits.
I use printf to print the result.

I got the read_line function from p. 365 of
_C Programming: A Modern Approach_, by K.N. King. Its prototype is

int read_line(char str[], int n);

I got the reverse function from p. 62 of _The C Programming Language_,
second edition, by Kernighan and Ritchie. Its prototype is

void reverse(char s[]);

This program will reverse any string; it doesn't have to be a string
of digits.

--Steve