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.

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

santosh wrote:

pete wrote:

Ajay wrote:

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

unsigned char bit_rev(unsigne d char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;

This is probably a stupid question, but why not simply do hi_mask =
128;?

Because a char /may/ contain more than 8 bits.

The statement
hi_mask = ((unsigned char)-1 >> 1) + 1;
will result in hi_mask having a char value that only has it's high order
bit on, no matter what size (in bits) a char is.

OTOH,
hi_mask = 128;
is only guaranteed to set /a/ bit (not necessarily the high order bit)
to one.

[snip]
- --

Lew Pitcher, IT Specialist, Corporate Technology Solutions,
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.2 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEIuJLagV FX4UWr64RAiPqAJ 46Gyhsr/6x/nXtNBsc8BGiJmow cACg2EUF
eKgfiLiLY8ze4Dr sXA3pT5Q=
=k/wz
-----END PGP SIGNATURE-----

[Charles Mills]

CBFalconer wrote:

Charles Mills wrote:

Charles Mills wrote:

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(un signed char b)
{
static const unsigned char b_tbl[] = {

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

};
return b_tbl[b];
}

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 */

Here is another non protable (but interesting) version based on code
from the book Hackers Delight:

#if CHAR_BIT != 8
# error ---> Code below only works on platforms with CHAR_BIT == 8
#endif
static unsigned char
reverse_byte(un signed char x)
{
x = (x & 0x55) << 1 | (x >> 1) & 0x55;
x = (x & 0x33) << 2 | (x >> 2) & 0x33;
x = (x & 0x0F) << 4 | (x >> 4) & 0x0F;
return x;
}

Nice divide and conquer approach
0x55 => 01010101
0x33 => 00110011
0x0F => 00001111

-Charlie

[santosh]

Lew Pitcher wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

santosh wrote:

pete wrote:

Ajay wrote:
Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.
unsigned char bit_rev(unsigne d char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;

This is probably a stupid question, but why not simply do hi_mask =
128;?

Because a char /may/ contain more than 8 bits.

The statement
hi_mask = ((unsigned char)-1 >> 1) + 1;
will result in hi_mask having a char value that only has it's high order
bit on, no matter what size (in bits) a char is.

OTOH,
hi_mask = 128;
is only guaranteed to set /a/ bit (not necessarily the high order bit)
to one.

[snip]

Thanks.

[Flash Gordon]

santosh wrote:

pete wrote:

Ajay wrote:

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

unsigned char bit_rev(unsigne d char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;

This is probably a stupid question, but why not simply do hi_mask =
128;?

Because there might be more than 8 bits in a byte. I used to work on
systems with 16 bit bytes regularly.

lo_mask = 1;
do {
if (!(byte & hi_mask) != !(byte & lo_mask)) {
byte ^= hi_mask | lo_mask;
}
hi_mask >>= 1;
lo_mask <<= 1;
} while (hi_mask > lo_mask);
return byte;
}

wow, that took me quite a while to figure out! Just out of curiosity,
is this the "most efficient" method to reverse bits that you know of?

That depends. On some systems it might be highly inefficient, on other
highly efficient.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

[Pedro Graca]

pete wrote:

Ajay wrote:

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

unsigned char bit_rev(unsigne d char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;

[snip rest of function definition]

Does this work for one's complement or any other representation of
negative numbers besides two's complement?

Maybe

hi_mask = (UCHAR_MAX + 1) >> 1;

is more portable?

--
If you're posting through Google read <http://cfaj.freeshell. org/google>

[CBFalconer]

santosh wrote:

jaysome wrote:

.... snip ...

(I just searched all 448 source files of one project I work on.
Only one references CHAR_BIT (yippee for me!). I wouldn't be
surprised if many of the regulars here would search their source
code and find 0 instances of use of CHAR_BIT. And I would be
eager to hear about how such lack of usage of CHAR_BIT affects
portability.)

My guess--kind of reiterated--is that those who know better will
get it right, and those that don't know better will, well, be
just fine.

Nevertheless, all other factor being equal, if there's a fully
portable way to do something, then that is to be preferred over
making assumptions and hard-coding values. That's the point
CBFalconer was making to Charles Mills.

Thank you. And, lacking that, document the assumption. E.G:

assert(8 == CHAR_BIT);

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

[pete]

Pedro Graca wrote:

pete wrote:

Ajay wrote:

Hi all,can you please tell the most efficient method to reverse a
byte.Function should return a byte that is reversed.
unsigned char bit_rev(unsigne d char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;

[snip rest of function definition]

Does this work for one's complement or any other representation of
negative numbers besides two's complement?

Yes.
Maybe

hi_mask = (UCHAR_MAX + 1) >> 1;

is more portable?

Not more portable, but slightly better style, perhaps.

(UCHAR_MAX == (unsigned char)-1) is always true,
regardless of the representation of negative integers.

N869
6.3.1.3 Signed and unsigned integers
[#1] When a value with integer type is converted to another
integer type other than _Bool, if the value can be
represented by the new type, it is unchanged.
[#2] Otherwise, if the new type is unsigned, the value is
converted by repeatedly adding or subtracting one more than
the maximum value that can be represented in the new type
until the value is in the range of the new type.

((unsigned char)-1 == -1 + UCHAR_MAX + 1)
((unsigned char)-1 == UCHAR_MAX )

--
pete

[pete]

pete wrote:

Pedro Graca wrote:

Maybe

hi_mask = (UCHAR_MAX + 1) >> 1;

is more portable?

Not more portable, but slightly better style, perhaps.

Actually, (UCHAR_MAX + 1) is not portable.

If UCHAR_MAX is equal to UINT_MAX, then
(hi_mask = (UCHAR_MAX + 1) >> 1)
is equal to zero.

--
pete

[Pedro Graca]

pete wrote:

Actually, (UCHAR_MAX + 1) is not portable.

If UCHAR_MAX is equal to UINT_MAX, then
(hi_mask = (UCHAR_MAX + 1) >> 1)
is equal to zero.

What about

hi_mask = (UCHAR_MAX >> 1) + 1;
--
If you're posting through Google read <http://cfaj.freeshell. org/google>

[pete]

Pedro Graca wrote:

pete wrote:

Actually, (UCHAR_MAX + 1) is not portable.

If UCHAR_MAX is equal to UINT_MAX, then
(hi_mask = (UCHAR_MAX + 1) >> 1)
is equal to zero.

What about

hi_mask = (UCHAR_MAX >> 1) + 1;

That's what I thought you had written when I replied
"Not more portable, but slightly better style, perhaps."

--
pete