reversing a byte

[Ajay]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

 

[Keith Thompson]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

By writing a function to do it. C would be a good choice of language
for this task.

Good luck.

If you want somebody else to do it for you, I'm sure you can find
someone willing to discuss consulting rates. If this is homework,
please give us your instructor's e-mail address so we can submit our
solutions directly.

And in anticipation of your next followup, please read
<http://cfaj.freeshell.org/google/>.

 

[Charles Mills]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

Use a look up table (untested generated code below):

static unsigned char
reverse_byte(unsigned char b)
{
static const unsigned char b_tbl[] = {
0xff, 0xfe, 0xfd, 0xfc, 0xfb, 0xfa, 0xf9, 0xf8,
0xf7, 0xf6, 0xf5, 0xf4, 0xf3, 0xf2, 0xf1, 0xf0,
0xef, 0xee, 0xed, 0xec, 0xeb, 0xea, 0xe9, 0xe8,
0xe7, 0xe6, 0xe5, 0xe4, 0xe3, 0xe2, 0xe1, 0xe0,
0xdf, 0xde, 0xdd, 0xdc, 0xdb, 0xda, 0xd9, 0xd8,
0xd7, 0xd6, 0xd5, 0xd4, 0xd3, 0xd2, 0xd1, 0xd0,
0xcf, 0xce, 0xcd, 0xcc, 0xcb, 0xca, 0xc9, 0xc8,
0xc7, 0xc6, 0xc5, 0xc4, 0xc3, 0xc2, 0xc1, 0xc0,
0xbf, 0xbe, 0xbd, 0xbc, 0xbb, 0xba, 0xb9, 0xb8,
0xb7, 0xb6, 0xb5, 0xb4, 0xb3, 0xb2, 0xb1, 0xb0,
0xaf, 0xae, 0xad, 0xac, 0xab, 0xaa, 0xa9, 0xa8,
0xa7, 0xa6, 0xa5, 0xa4, 0xa3, 0xa2, 0xa1, 0xa0,
0x9f, 0x9e, 0x9d, 0x9c, 0x9b, 0x9a, 0x99, 0x98,
0x97, 0x96, 0x95, 0x94, 0x93, 0x92, 0x91, 0x90,
0x8f, 0x8e, 0x8d, 0x8c, 0x8b, 0x8a, 0x89, 0x88,
0x87, 0x86, 0x85, 0x84, 0x83, 0x82, 0x81, 0x80,
0x7f, 0x7e, 0x7d, 0x7c, 0x7b, 0x7a, 0x79, 0x78,
0x77, 0x76, 0x75, 0x74, 0x73, 0x72, 0x71, 0x70,
0x6f, 0x6e, 0x6d, 0x6c, 0x6b, 0x6a, 0x69, 0x68,
0x67, 0x66, 0x65, 0x64, 0x63, 0x62, 0x61, 0x60,
0x5f, 0x5e, 0x5d, 0x5c, 0x5b, 0x5a, 0x59, 0x58,
0x57, 0x56, 0x55, 0x54, 0x53, 0x52, 0x51, 0x50,
0x4f, 0x4e, 0x4d, 0x4c, 0x4b, 0x4a, 0x49, 0x48,
0x47, 0x46, 0x45, 0x44, 0x43, 0x42, 0x41, 0x40,
0x3f, 0x3e, 0x3d, 0x3c, 0x3b, 0x3a, 0x39, 0x38,
0x37, 0x36, 0x35, 0x34, 0x33, 0x32, 0x31, 0x30,
0x2f, 0x2e, 0x2d, 0x2c, 0x2b, 0x2a, 0x29, 0x28,
0x27, 0x26, 0x25, 0x24, 0x23, 0x22, 0x21, 0x20,
0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18,
0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10,
0xf, 0xe, 0xd, 0xc, 0xb, 0xa, 0x9, 0x8,
0x7, 0x6, 0x5, 0x4, 0x3, 0x2, 0x1, 0x0
};
return b_tbl;
}

-Charlie

 

[Charles Mills]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

Use a look up table (untested generated code below):

static unsigned char
reverse_byte(unsigned char b)
{
static const unsigned char b_tbl[] = {

---8<---- sniped totally wrong lookup table ---8<----

};
return b_tbl;
}

-Charlie

probably want something like this:
static const unsigned char b_tbl[] = {
0x0, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
...,
0xf, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};

you can fill in the blanks.

-Charlie

 

[Charles Mills]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

Use a look up table (untested generated code below):

static unsigned char
reverse_byte(unsigned char b)
{
static const unsigned char b_tbl[] = {

---8<---- sniped totally wrong lookup table ---8<----

};
return b_tbl;
}

-Charlie

probably want something like this:
static const unsigned char b_tbl[] = {
0x0, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
...,
0xf, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};

you can fill in the blanks.

-Charlie

 

[sudharsan]

Hi
I give here a piece of code to reverse a byte but iam not sure how good
it is...

unsigned int n=0x01;
unsinged int c=0x00;
int i;
/* b is given byte */
for( i=0; i<8 ;i++)
{
if( b & n) { c=c + 1;}
c<<1;
n<<1;
}
/* the reversed value is stored in c */

 

[CBFalconer]

Ajay wrote:

Hi all,can you please tell the most efficient method to reverse
a byte.Function should return a byte that is reversed.

Use a look up table (untested generated code below):

static unsigned char
reverse_byte(unsigned char b)
{
static const unsigned char b_tbl[] = {

---8<---- sniped totally wrong lookup table ---8<----

};
return b_tbl;
}

probably want something like this:
static const unsigned char b_tbl[] = {
0x0, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
...,
0xf, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};

you can fill in the blanks.

Works like a charm, NOT, when CHAR_BIT > 8. i.e. document hidden
assumptions. In order of execution:

unsigned char* b_tbl = malloc(1 + UCHAR_MAX);
...
/* code to initialize table, after checking it is non-NULL. */
...
/* code that uses the table */

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

 

[Vladimir S. Oka]

sudharsan wrote:

Don't top-post. I've corrected it here...

Hi
I give here a piece of code to reverse a byte but iam not sure how good
it is...

Why bother posting untested and uncompilable code in response to
someone's question?

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

int main(void)
{

unsigned int n=0x01;
unsinged int c=0x00;

You surely mean:

unsigned int c = 0x00;

unsigned int b = 15;

int i;
/* b is given byte */
for( i=0; i<8 ;i++)
{
if( b & n) { c=c + 1;}

You never declare `b`, let alone assign it value.

c<<1;
n<<1;

These two do precisely nothing (useful);

}
/* the reversed value is stored in c */

printf("b = %d, c = %d\n", b, c);

return 0;
}

So the result is "b = 15, c = 8", `c` being 8 for any `b`.

any one please correct this if any wrong.

I've corrected above it so it will compile and run. Now it's your turn
to correct the logic. You did have an idea how to do this, didn't you?

 

[santosh]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

Your question is not very clear. Do you need to reverse the *value* of
the bits in a byte or do you need to reverse their *position*? If you
need to do the former, you can use C's complement operator, (~). If the
latter, you'll need to write a function to do it. If you want it to be
very fast, probably using a 256 byte look-up table is the way to go.

 

[Pedro Graca]

I give here a piece of code to reverse a byte but iam not sure how good
it is...

Well, I'm not commenting on how good it is ... but
a) it's not portable.
b) you could have posted the full function definition
along with the comments about `b` and `c`.
c) it's very poorly indented.
d) your use of whitespace is very strange.


#include <limits.h> /* for CHAR_BIT */

unsigned int reverse_byte(unsigned int b) {

unsigned int n=0x01;
unsinged int c=0x00;
int i;
/* b is given byte */

#if 0

for( i=0; i<8 ;i++)

#endif

/* Why do you assume a byte is 8 bits? */
for( i=0; i<CHAR_BIT ;i++)

{
if( b & n) { c=c + 1;}
c<<1;
n<<1;
}
/* the reversed value is stored in c */

return c;
}

 

[Eric Sosman]

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.

Whence this unhealthy fascination with "most efficient?"
Two minutes ago you asked for the "most efficient" way to find
a substring, now you're asking for the "most efficient" way
to reverse a byte. What's next? The "most efficient" way to
listen to the Emperor Concerto?

For future reference: The C language says nothing about the
amount of time any operation requires, nothing about the amount
of space any executable code occupies, nothing about the power
consumption of the computer running the code, and very little
about the amount of space taken by data objects. Most notions
of "efficiency" incorporate one or more of these measures, so
questions about "efficiency" are usually unanswerable in terms
of C. They may be answerable for a particular implementation of
C on a particular computer, but in that case you should read
the documentation for that implementation or ask your question
in a forum devoted to that implementation; this is the wrong
forum for such questions.

... and if you'll accept a tiny bit of advice from a battle-
scarred veteran: "efficiency" is not the most important attribute
of a program. For example, here is the most "efficient" method
I can think of to solve your byte-reversal problem:

#define REVERSE_BYTE(x) 0

On most machines this will be faster and shorter than almost any
alternative you can come up with, and sometimes it will even give
the right answer. Use it in good health.

 

[Ajay]

Hi Eric,Firsto of all thanks for the solution.I understand here what
you want to say but i think in any language(specially in C
language)implementation of algorithm is the most importent thing.this
is not about a simple question like this.But the habbit to think
differently start from this point.All the big companies i have gone for
ask only for efficient and fast solution(with respect to
memory/speed).Anybody can make program..isn't it?bt it depend how you
make it.
I appreciate for your solution but i want to impement the program on my
own.See if you can help me out---
Function prototype shuold be Byte * Reverse(byte)

where byte for example:--- 11100010
output should be ---------- 01000111

 

[Vladimir S. Oka]

Hi Eric,Firsto of all

Quote context! Read:

<http://cfaj.freeshell.org/google/>

thanks for the solution.I understand here what
you want to say but i think in any language(specially in C
language)implementation of algorithm is the most importent thing.this
is not about a simple question like this.But the habbit to think
differently start from this point.All the big companies i have gone for
ask only for efficient and fast solution(with respect to
memory/speed).Anybody can make program..isn't it?bt it depend how you
make it.

The right approach is:

1. code it in a readable and correct fashion
2. *mesure*
3. if 2. is unsatisfactory, only then improve efficiency

If you don't plan on doing 2., the rules of optimisation are:

1. Don't do it
2. (experts only) Don't do it yet.

I appreciate for your solution but i want to impement the program on my
own.See if you can help me out---
Function prototype shuold be Byte * Reverse(byte)

where byte for example:--- 11100010
output should be ---------- 01000111

By writing it for you? Fat chance!

 

[Pierre Maurette]

Ajay, le 22/03/2006 a écrit :
[...]

Function prototype shuold be Byte * Reverse(byte)

where byte for example:--- 11100010
output should be ---------- 01000111

several ways here:
http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

You can choose calculation methods for short code, lookup table method
for fast code.

You can use your own code for a calculation method generating the
lookup table (text) and copy-paste in your final code.

When you have Reverse(), you check Reverse(Reverse()) is identity.

 

[Richard G. Riley]

Whence this unhealthy fascination with "most efficient?"
Two minutes ago you asked for the "most efficient" way to find
a substring, now you're asking for the "most efficient" way
to reverse a byte. What's next? The "most efficient" way to
listen to the Emperor Concerto?

Whereas I agree with your general concensus that an unhealthy
obsession with speed can lead to buggy and convoluted code, it is
also, often the case that the efficient way is also the easiest and
most reliable way in a relatively low level language such as C. The
fact that its a byte being talked about suggests that the reversal is
required in a byte/character orientated arena where efficiency and cpu
cycles do need to be saved. I would not, however, counter sticking
setjmps in or gotos to save a few cycles for non critical function
return replacement : especially if the contents of those functions
were to contain the bulk of the work. Its a % game.

For new programmers, a lot of employers are interested in their
abilities to maximise the performance of a C program while maintaining
readability and maintability. This group can, and does, help in that
education.

For future reference: The C language says nothing about the
amount of time any operation requires, nothing about the amount
of space any executable code occupies, nothing about the power
consumption of the computer running the code, and very little
about the amount of space taken by data objects. Most notions

No, but it is a language picked for its brevity and efficiency : a fair
programmer can almost see the instructions generated and frequently
pick the language for just that feature. There is a reason that Java
or Perl or somesuch is not used for writing 3d modelling engines
expected to render 32 bit graphics in real time.

of "efficiency" incorporate one or more of these measures, so
questions about "efficiency" are usually unanswerable in terms
of C. They may be answerable for a particular implementation of
C on a particular computer, but in that case you should read
the documentation for that implementation or ask your question
in a forum devoted to that implementation; this is the wrong
forum for such questions.

I dont agree. It is a forum for the discussion of the C Language : and
how to do something is as on topic as the result of that procedure. To
suggest that looking for efficiency is not a good thing with a
language like C is suggesting that aiming for structured classes in
Java or C++ is counterproductive to achieving the result.

Efficient code does not have to be nasty code.

... and if you'll accept a tiny bit of advice from a battle-
scarred veteran: "efficiency" is not the most important attribute
of a program. For example, here is the most "efficient" method
I can think of to solve your byte-reversal problem:

#define REVERSE_BYTE(x) 0

On most machines this will be faster and shorter than almost any
alternative you can come up with, and sometimes it will even give
the right answer. Use it in good health.

To the OP : since a byte is only representing (generally..) 8 bits or
256 values then you could look up in an array which you initialise at
program start. Efficient. Else, test bit 0 of source byte, if set then
set bit 0 of destination word. Left shift dest, right shift
source. Repeat 8 times. Look up how to calculate number of bits to be
portable. There may be better ways.

Good luck!

 

[Keith Thompson]

Hi Eric,Firsto of all thanks for the solution.I understand here what
you want to say but i think in any language(specially in C
language)implementation of algorithm is the most importent thing.this
is not about a simple question like this.But the habbit to think
differently start from this point.All the big companies i have gone for
ask only for efficient and fast solution(with respect to
memory/speed).Anybody can make program..isn't it?bt it depend how you
make it.
I appreciate for your solution but i want to impement the program on my
own.See if you can help me out---
Function prototype shuold be Byte * Reverse(byte)

If you want to implement it on your own, what are you asking us for?
(That's a serious question.)

Your prototype:

Byte *Reverse(byte)

looks odd. There is no predefined type "Byte" or "byte" in C (those
are two different identifiers), and I can't imagine why you'd want to
return a pointer. You probably want

unsigned char reverse(unsigned char *x);

where byte for example:--- 11100010
output should be ---------- 01000111

And please read <http://cfaj.freeshell.org/google/> if you want anyone
to know what you're talking about.

 

[Keith Thompson]

Your prototype:

Byte *Reverse(byte)

looks odd. There is no predefined type "Byte" or "byte" in C (those
are two different identifiers), and I can't imagine why you'd want to
return a pointer. You probably want

unsigned char reverse(unsigned char *x);

Sorry, I *really* didn't want the '*' there. The prototype should be

unsigned char reverse(unsigned char x);

 

[CBFalconer]

.... snip ...

No, but it is a language picked for its brevity and efficiency :
a fair programmer can almost see the instructions generated and
frequently pick the language for just that feature. There is a
reason that Java or Perl or somesuch is not used for writing 3d
modelling engines expected to render 32 bit graphics in real time.

For a minority, yes. It seems to me that the majority of
programmers today wouldn't recognize a conditional jump, or an
indirect reference, in assembly code if it jumped up and bit them
on the gluteus maximus.

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

 

[code break]

Hi all,can you please tell the most efficient method to reverse a

efficient here is compact code or compact logic not other stuffs..

 

[jaysome]

Ajay wrote:

Hi all,can you please tell the most efficient method to reverse
a byte.Function should return a byte that is reversed.

Use a look up table (untested generated code below):

static unsigned char
reverse_byte(unsigned char b)
{
static const unsigned char b_tbl[] = {

---8<---- sniped totally wrong lookup table ---8<----

};
return b_tbl;
}

probably want something like this:
static const unsigned char b_tbl[] = {
0x0, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
...,
0xf, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};

you can fill in the blanks.

Works like a charm, NOT, when CHAR_BIT > 8. i.e. document hidden
assumptions. In order of execution:

True, but I highly suspect that the OP will ever use an implementation
that defines "CHAR_BIT > 8". Nor would I suspect that most other C
programmers will.