reversing a byte

[Richard Heathfield]

jaysome said:

[...] I highly suspect that the OP will ever use an implementation
that defines "CHAR_BIT > 8".

If he sticks with C, it's almost inevitable in the long run.

Nor would I suspect that most other C programmers will.

Well, I certainly have used such an implementation, and so have a whole
bunch of people I was working with at the time, and so has anyone else who
has written C for the same chip, and so have lots of other people writing C
for other similar chips, too. And such chips, common a few years ago, are
becoming yet more common all the time.

 

[jaysome]

jaysome said:

[...] I highly suspect that the OP will ever use an implementation
that defines "CHAR_BIT > 8".

If he sticks with C, it's almost inevitable in the long run.

Nor would I suspect that most other C programmers will.

Well, I certainly have used such an implementation, and so have a whole
bunch of people I was working with at the time, and so has anyone else who
has written C for the same chip, and so have lots of other people writing C
for other similar chips, too. And such chips, common a few years ago, are
becoming yet more common all the time.

Okay.

But the fact that you and your co-workers and probably some of your
friends and their friends have used such an implementation does not
hardly qualify for "most" C programmers. After all, you are a revered
mavin here in c.l.c., and you most likely attract others of your type

To be sure--a table impementation is fine as long as you understand the
ramifications to portability. And I reiterate--most C programmers will
be just fine, whether of not they understand the ramifications.

 

[Vladimir S. Oka]

jaysome said:

[...] I highly suspect that the OP will ever use an implementation
that defines "CHAR_BIT > 8".

If he sticks with C, it's almost inevitable in the long run.

Nor would I suspect that most other C programmers will.

Well, I certainly have used such an implementation, and so have a whole
bunch of people I was working with at the time, and so has anyone else who
has written C for the same chip, and so have lots of other people writing C
for other similar chips, too. And such chips, common a few years ago, are
becoming yet more common all the time.

Okay.

But the fact that you and your co-workers and probably some of your
friends and their friends have used such an implementation does not
hardly qualify for "most" C programmers. After all, you are a revered
mavin here in c.l.c., and you most likely attract others of your type

To be sure--a table impementation is fine as long as you understand the
ramifications to portability.

That's fair enough.

And I reiterate--most C programmers will
be just fine, whether of not they understand the ramifications.

Can I borrow your crystal ball, please. I'm going to the races. ;-)

How can you be so sure that the next Big Thing in processors won't
have, say, 16 for CHAR_BIT? How long did it take from Intel 4004 to
80386? [non-ASCII native moan: After all, it's high time `char` really
becoming able to represent characters from more than a handful of
languages, without making us jump through hoops.]

Also, it's not necessarilly /today's/ programmers, rather the ones that
will maintain their code, or try to port it to future architectures.

 

[jaysome]

Richard Heathfield wrote:

jaysome said:



[...] I highly suspect that the OP will ever use an implementation
that defines "CHAR_BIT > 8".


If he sticks with C, it's almost inevitable in the long run.




Nor would I suspect that most other C programmers will.


Well, I certainly have used such an implementation, and so have a whole
bunch of people I was working with at the time, and so has anyone else who
has written C for the same chip, and so have lots of other people writing C
for other similar chips, too. And such chips, common a few years ago, are
becoming yet more common all the time.

Okay.

But the fact that you and your co-workers and probably some of your
friends and their friends have used such an implementation does not
hardly qualify for "most" C programmers. After all, you are a revered
mavin here in c.l.c., and you most likely attract others of your type

To be sure--a table impementation is fine as long as you understand the
ramifications to portability.

That's fair enough.

And I reiterate--most C programmers will
be just fine, whether of not they understand the ramifications.

Can I borrow your crystal ball, please. I'm going to the races. ;-)

How can you be so sure that the next Big Thing in processors won't
have, say, 16 for CHAR_BIT?

When, and if, that happens, Microsoft, or some Open Source developers,
will put out an announcement stating that your existing C programs may
be in jeapordy if you have, in arguably a pedantic manner, assumed that
"CHAR_BIT == 8".

(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.

 

[Vladimir S. Oka]

Richard Heathfield wrote:
jaysome said:

[...] I highly suspect that the OP will ever use an implementation
that defines "CHAR_BIT > 8".

If he sticks with C, it's almost inevitable in the long run.

Nor would I suspect that most other C programmers will.

Well, I certainly have used such an implementation, and so have a whole
bunch of people I was working with at the time,

That's fair enough.


Can I borrow your crystal ball, please. I'm going to the races. ;-)

How can you be so sure that the next Big Thing in processors won't
have, say, 16 for CHAR_BIT?

When, and if, that happens, Microsoft, or some Open Source developers,
will put out an announcement stating that your existing C programs may
be in jeapordy if you have, in arguably a pedantic manner, assumed that
"CHAR_BIT == 8".

You mean like for Y2K problem: s*itloads of money and time will be
spent fixing the avoidable mess?

(I just searched all 448 source files of one project I work on. Only one
references CHAR_BIT (yippee for me!).

Relevant only if your code /relies/ on CHAR_BIT size.

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.

I'd really like that crystal ball of yours...

And I would be eager to hear about how such lack of
usage of CHAR_BIT affects portability.)

Say your code relies on the fact that CHAR_BIT is 8 (or any other
value), and you use a table of 256 values for reversing a `char`
(sounds familiar?). Now, try to re-compile for the architecture with
CHAR_BIT being 9. See the point? I guess even your neat utility that
generates the said table relies on CHAR_BIT being 8, so re-compiling,
and re-running that doesn't help either. Now, where in all those 448
(or 1448, or 11448) source files was that pesky table?!

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.

They may be "just fine", I'm worried about someone (possibly me) having
to maintain and port their code, not to mention the possibility of
Ariane, Therac-25 and similar.

 

[santosh]

When, and if, that happens, Microsoft, or some Open Source developers,
will put out an announcement stating that your existing C programs may
be in jeapordy if you have, in arguably a pedantic manner, assumed that
"CHAR_BIT == 8".

(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.

 

[osmium]

:

Works like a charm, NOT, when CHAR_BIT > 8. i.e. document hidden
assumptions.

Can we back up here?

The OP wanted to get a job, right? He was asked a stupid question, since
there are at least three ways to measure efficiency - footprint, speed,
programmer's time and clarity etc. The OP has two choices, he can say "WTF
do you mean" or he can give the answer this doofus actually wants, a table
look up. Is there even the tiniest doubt that that was the desired answer
to successfully continue the interview? Do you really think this guy
(hopefully from "Human Resources") cares or even knows about peculiar
representations of characters?

 

[Vladimir S. Oka]

:



Can we back up here?

The OP wanted to get a job, right? He was asked a stupid question, since
there are at least three ways to measure efficiency - footprint, speed,
programmer's time and clarity etc. The OP has two choices, he can say "WTF
do you mean" or he can give the answer this doofus actually wants, a table
look up. Is there even the tiniest doubt that that was the desired answer
to successfully continue the interview? Do you really think this guy
(hopefully from "Human Resources") cares or even knows about peculiar
representations of characters?

If I was interviewed on C skills by an HR drone, I'd say "thank you"
and leave there and then. If I thought the engineer interviewing me
didn't "care or even know" about such things, I'd run as fast as I
could. If neither was the case, I'd expect to be grilled on just such
an point.

 

[CBFalconer]

jaysome wrote:
.... snip ...

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]

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(unsigned char byte)
{
unsigned hi_mask, lo_mask;

hi_mask = ((unsigned char)-1 >> 1) + 1;
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;
}

 

[santosh]

unsigned char bit_rev(unsigned 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;?

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?

 

[Lew Pitcher]

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

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

iD8DBQFEIuJLagVFX4UWr64RAiPqAJ46Gyhsr/6x/nXtNBsc8BGiJmowcACg2EUF
eKgfiLiLY8ze4DrsXA3pT5Q=
=k/wz
-----END PGP SIGNATURE-----

 

[Flash Gordon]

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.

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.

 

[Charles Mills]

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

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(unsigned 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]

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

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.

 

[Pedro Graca]

unsigned char bit_rev(unsigned 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?

 

[pete]

unsigned char bit_rev(unsigned 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]

Pedro Graca wrote:

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.

 

[Pedro Graca]

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;

 

[pete]

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