reverse byte

[Kapil Khosla]

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

 

[Allan Bruce]

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

Create a temp Byte and AND the original byte with mask 0x1 to see if there
is a 1 in the LSB.
If there is a 1 then OR 0x80 to the temp byte

Now AND the original with 0x2 and if its a 1 then OR the temp with 0x4

And so on.

HTH
Allan

 

[Kevin Easton]

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.

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

- Kevin.

 

[Jirka Klaue]

http://graphics.stanford.edu/~seander/bithacks.html

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

That might be true. But it's not very helpful.
How is the lookup table generated? You wouldn't do this by hand, would you?

Jirka

 

[Robert Stankowic]

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.

OK, fireproof suit and helmet on....

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

int main(void)
{
unsigned char in = 0;
unsigned char out;
int i;
int j;

for(j = 1; j <= UCHAR_MAX ; j++)
{
in = (unsigned char)j;
printf("in %x", (unsigned)in);
for(i = 0, out = 0; i < CHAR_BIT; i++)
{
in >>= (i != 0);
out <<= (i != 0);
out = (unsigned char)(out | (in & 1));
}
out = (unsigned char)(out | (in & 1));
printf(" out %x\n", (unsigned)out);
}
}

Critique and improvrment suggestions welcome
Especially about the casts...
Robert

 

[Robert Stankowic]

OK, fireproof suit and helmet on....

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

int main(void)
{
unsigned char in = 0;
unsigned char out;
int i;
int j;

for(j = 1; j <= UCHAR_MAX ; j++)
{
in = (unsigned char)j;
printf("in %x", (unsigned)in);
for(i = 0, out = 0; i < CHAR_BIT; i++)
{
in >>= (i != 0);
out <<= (i != 0);
out = (unsigned char)(out | (in & 1));
}
out = (unsigned char)(out | (in & 1));

Oops, drop the statement above - sorry

 

[pete]

Create a temp Byte and AND the original byte
with mask 0x1 to see if there is a 1 in the LSB.
If there is a 1 then OR 0x80 to the temp byte

You don't start with 0x80 on clc.

step 1
Use unsigned char for mask variables.
One portable expression for the initial value of the high mask is:
(((unsigned char)-1 >> 1) + 1)
As stated, 1 is the initial value for the low mask.

step 2
Do a bitwise AND of the high mask and the byte, and
a bitwise AND of the low mask and the byte.

step 3
If the results of the bitwise ANDs are not either both zero
or both nonzero, then the values of the bits being tested
are different and they should be flipped.
One way to do that, would be to XOR the value of the byte
with the result of a bitwise OR of the two masks,
and change the value of the byte to the XOR result.

step 4
Change the values of the high and low mask.
Shift the high mask right by 1 and shift the low mask left by 1.

step 5
If the high mask is greater than the low mask,
then repeat, starting at step 2.

 

[Jirka Klaue]

Robert Stankowic wrote:
....

Oops, drop the statement above - sorry

And drop the cast, too. The result of (out | (in & 1)) is assigned
to an an unsigned char. The cast is redundant.

Jirka

 

[pete]

Oops, drop the statement above - sorry

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

int main(void)
{
unsigned in;
unsigned out;
int i;
unsigned char j;

j = 0;
while (++j != 0) {
in = j;
printf("in %x", in);
for (i = 0, out = 0; i < CHAR_BIT; i++) {
in >>= (i != 0);
out <<= (i != 0);
out |= in & 1;
}
printf(" out %x\n", out);
}
return 0;
}

 

[Joe Wright]

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

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?

 

[pete]

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

int main(void)
{
unsigned in;
unsigned out;
int i;
unsigned char j;

j = 1;
do {
in = j;
printf("in %x", in);
i = 1;
out = in & 1;
do {
in >>= 1;
out <<= 1;
out |= in & 1;
++i;
} while (CHAR_BIT > i);
printf(" out %x\n", out);
} while (++j != 0);
return 0;
}

 

[Robert Stankowic]

Robert Stankowic wrote:
...

And drop the cast, too. The result of (out | (in & 1)) is assigned
to an an unsigned char. The cast is redundant.

Aren't integer promotions coming into play here?
At least my compiler warns about assigning an int to a char..

Robert

 

[Jirka Klaue]

Aren't integer promotions coming into play here?
At least my compiler warns about assigning an int to a char..

That's the only reason for the cast: Tell the compiler to stop whining.

Jirka

 

[Robert Stankowic]

Aren't integer promotions coming into play here?
At least my compiler warns about assigning an int to a char..

Oviously not. Blind spot, sorry.
Robert

 

[Kapil Khosla]

Thanks a lot !
I figured out using that hint.

Kapil

 

[Jack Klein]

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

- Kevin.

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.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Default User]

That might be true. But it's not very helpful.
How is the lookup table generated? You wouldn't do this by hand, would you?

Do what I did, google for one, copy it into your code, presto. Here's
mine:


#define REVERSEBITS(b) (BitReverseTable)

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

 

[Jack Klein]

OK, fireproof suit and helmet on....

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

int main(void)
{
unsigned char in = 0;
unsigned char out;
int i;
int j;

for(j = 1; j <= UCHAR_MAX ; j++)

Not all that common (except to embedded programmers like me), but
there is the distinct possibility that UCHAR_MAX is > INT_MAX.
Infinite loop.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Christopher Benson-Manica]

That might be true. But it's not very helpful.
How is the lookup table generated? You wouldn't do this by hand, would you?

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

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <string.h>

char buf[CHAR_BIT+1];

void get_binary( int n )
{
int i;

for( i=0 ; i < CHAR_BIT ; i++ ) {
if( n % 2 ) {
buf[CHAR_BIT-i-1]='1';
}
else {
buf[CHAR_BIT-i-1]='0';
}
n/=2;
}
}

int main(void)
{
const int size=pow( 2, CHAR_BIT );
char **table;
int i;

buf[CHAR_BIT]=0;
printf( "%s\n", buf );
/* Error checking on malloc() omitted */
table=malloc( size * sizeof(char *) );
for( i=0 ; i < size ; i++ ) {
table=malloc( (1+CHAR_BIT) * sizeof(char) );
get_binary( i );
strcpy( table, buf );
}

for( i=0; i < size ; i++ ) {
printf( "%s\n", table );
}

return EXIT_SUCCESS;
}

 

[Robert Stankowic]

Not all that common (except to embedded programmers like me), but
there is the distinct possibility that UCHAR_MAX is > INT_MAX.
Infinite loop.

Shudder

OK
unsigned i;
unsigned j;
Better?

Thanks
kind regards
Robert