By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,110 Members | 1,010 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,110 IT Pros & Developers. It's quick & easy.

efficiency match.

P: n/a
THE GAME :

Write a C function to swap the bits of a char so
that its bits would become the mirror image of the
char.MSBs become its LSBs etc. E.g. 11001100
binary would become 00110011 binary.

---------------------------------------

Sep 4 '06 #1
Share this Question
Share on Google+
77 Replies


P: n/a
"Aman JIANG" <Am*******@gmail.comwrote:
THE GAME :

Write a C function to swap the bits of a char so
that its bits would become the mirror image of the
char.MSBs become its LSBs etc. E.g. 11001100
binary would become 00110011 binary.
Well? Go ahead, demonstrate your work so far. It's your homework, not
ours.

Richard
Sep 4 '06 #2

P: n/a
Aman JIANG said:
THE GAME :

Write a C function to swap the bits of a char so
that its bits would become the mirror image of the
char.MSBs become its LSBs etc. E.g. 11001100
binary would become 00110011 binary.
THE RULES:

Try it yourself first, and if you can't do it, post your best-effort code so
that we can help you fix it.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 4 '06 #3

P: n/a
it is just complement operation, can be done using ~ operator.

Sep 4 '06 #4

P: n/a
ravichoudhari wrote:
it is just complement operation, can be done using ~ operator.
Which makes me wonder , what's the group's position
regarding misleading advice on homework questions
when the person posting the question hasn't done any
work at all ?

Sep 4 '06 #5

P: n/a
ravichoudhari said:
it is just complement operation, can be done using ~ operator.
For the example posted, that would work. But it would not give a true mirror
image on many inputs. Using ~, 10000000 would become 01111111 rather than
00000001.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 4 '06 #6

P: n/a
Richard Heathfield a écrit :
ravichoudhari said:

>>it is just complement operation, can be done using ~ operator.


For the example posted, that would work. But it would not give a true mirror
image on many inputs. Using ~, 10000000 would become 01111111 rather than
00000001.
Yes but that's this guy problem. If he asks other people to do his/her
homework he can't ask also for correct answers :-)

Sep 4 '06 #7

P: n/a
hi man,
This is NOT my homework.

Sep 4 '06 #8

P: n/a
Aman JIANG wrote:
hi man,
This is NOT my homework.
/What/ isn't your homework?

Quote (and trim) as appropriate.

--
Chris "usenet is nobody's homework" Dollin
A rock is not a fact. A rock is a rock.

Sep 4 '06 #9

P: n/a
Aman JIANG wrote:
THE GAME :

Write a C function to swap the bits of a char so
that its bits would become the mirror image of the
char.MSBs become its LSBs etc. E.g. 11001100
binary would become 00110011 binary.
This is exciting! Here's my attempt. I hope it's of use to you. I haven't
really tested it thoroughly, so I hope there are no mistakes.

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

int swap_bits(int b) {
int result = 0;
char digits[CHAR_BIT + 1];
char digits_rev[CHAR_BIT + 1] = {0};
int n;
for (n = 0; n != CHAR_BIT; ++n) {
sprintf(digits + n, "%i", !!((1 << n) & b));
}
for (n = 0; n != CHAR_BIT; ++n) {
digits_rev[n] = digits[CHAR_BIT - n - 1];
}
for (n = 0; n != CHAR_BIT; ++n) {
result |= (digits_rev[n] - '0') << n;
}
return result;
}

S.
Sep 4 '06 #10

P: n/a
unsigned char RevChar(unsigned char Byte)
{
typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));
tpname byte = (tpname)Byte;
return (unsigned char)
(((byte & 128) >7)
| ((byte & 64) >5)
| ((byte & 32) >3)
| ((byte & 16) >1)
| ((byte & 8) << 1)
| ((byte & 4) << 3)
| ((byte & 2) << 5)
| ((byte & 1) << 7));
}

Yes... Yes... and ALL jeerer here,
can you overtake me on performance ?

if you can, this is my homework.
BUT if you can't, it's just ur homework, okay ?

PS: donnot use TABLE plz.

Sep 4 '06 #11

P: n/a
Aman JIANG posted:
unsigned char RevChar(unsigned char Byte)
{
typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));
tpname byte = (tpname)Byte;
return (unsigned char)
(((byte & 128) >7)
| ((byte & 64) >5)
| ((byte & 32) >3)
| ((byte & 16) >1)
| ((byte & 8) << 1)
| ((byte & 4) << 3)
| ((byte & 2) << 5)
| ((byte & 1) << 7));
}

Since when is a byte eight bits?

If I wanted to mirror-image an unsigned char, I'd probably start off with
something like:

#include <limits.h>

char unsigned Mirror(char unsigned const val_byte)
{
unsigned const val = val_byte;

unsigned mirror = 0;

unsigned single_bit_val = 1U << CHAR_BIT-1;
unsigned single_bit_mirror = 1;

do
{
if(val & single_bit_val) mirror |= single_bit_mirror;
else mirror &= ~single_bit_mirror;
}
while(single_bit_mirror <<= 1,
(single_bit_val >>= 1) != (unsigned)UCHAR_MAX+1);

return mirror;
}

--

Frederick Gotham
Sep 4 '06 #12

P: n/a
Frederick Gotham wrote:
Since when is a byte eight bits?

If I wanted to mirror-image an unsigned char, I'd probably start off with
something like:


Yes, eight bits.
and... was ur code right ?

Sep 4 '06 #13

P: n/a
Aman JIANG wrote:
unsigned char RevChar(unsigned char Byte)
{
typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));
tpname byte = (tpname)Byte;
return (unsigned char)
(((byte & 128) >7)
| ((byte & 64) >5)
| ((byte & 32) >3)
| ((byte & 16) >1)
| ((byte & 8) << 1)
| ((byte & 4) << 3)
| ((byte & 2) << 5)
| ((byte & 1) << 7));
}

Yes... Yes... and ALL jeerer here,
can you overtake me on performance ?
Possibly. The C Standard says nothing about the speeds
of operations on different data types, which are inherently
implementation-dependent. On some machines, though, it will
turn out that `unsigned long' arithmetic is slower than the
ordinary `int' arithmetic you would get if you were to
work directly with `byte' instead of with `Byte'.[*]

Here's an easy optimization, though: Get rid of the
completely pointless assert() call. It asserts nothing that
is of any importance to the code, and if it takes any time
that time is pure waste.
[*] On some systems, arithmetic on `byte' will be done
in `unsigned int' rather than in `int'. However, such systems
use a character that's at least sixteen bits wide, so your
code would be wrong anyhow.
if you can, this is my homework.
BUT if you can't, it's just ur homework, okay ?

PS: donnot use TABLE plz.
Why not? Did your teacher forbid it?

--
Eric Sosman
es*****@acm-dot-org.invalid
Sep 4 '06 #14

P: n/a
Frederick Gotham wrote:
>
.... snip ...
>
Since when is a byte eight bits?
Since an octal 7400 series buffer cost one dollar.

--
"The French have no word for entrepreneur." - George W. Bush
"Those who enter the country illegally violate the law."
- George W. Bush in Tucson, Ariz., Nov. 28, 2005
"I hear the voices". - G W Bush, 2006-04-18

Sep 4 '06 #15

P: n/a
jacob navia said:
Richard Heathfield a écrit :
>ravichoudhari said:

>>>it is just complement operation, can be done using ~ operator.


For the example posted, that would work. But it would not give a true
mirror image on many inputs. Using ~, 10000000 would become 01111111
rather than 00000001.

Yes but that's this guy problem. If he asks other people to do his/her
homework he can't ask also for correct answers :-)
I agree. I did not provide a correct answer. I merely commented on an
incorrect answer.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 4 '06 #16

P: n/a
>Since when is a byte eight bits?
CBFalconer posted:
Since an octal 7400 series buffer cost one dollar.
Aman JIANG posted:
Yes, eight bits.

The quantity of bits which comprises a byte is implementation-defined and can
be determined from the macro CHAR_BIT.

Even if 99.9999% of machines have 8-Bit bytes, that has no bearing whatsover
on the definition of the specification of the C Programming Language.

I would expect your original function to check for 8-Bit bytes:

#include <limits.h>

void Func(void)
{
#if CHAR_BIT != 8
#error "This code is not Standard C code -- bytes must be 8-Bit."
#endif
}

--

Frederick Gotham
Sep 4 '06 #17

P: n/a
Eric Sosman wrote:
Why not? Did your teacher forbid it?
1. I am NOT a Student. OK?
2. TABLE is NOT a true algorithm for this.

Sep 4 '06 #18

P: n/a
Frederick Gotham wrote:
The quantity of bits which comprises a byte is implementation-defined and can
be determined from the macro CHAR_BIT.

Even if 99.9999% of machines have 8-Bit bytes, that has no bearing whatsover
on the definition of the specification of the C Programming Language.
Alright.
but i think u must make ur code work right first.

Sep 4 '06 #19

P: n/a
Aman JIANG wrote:
unsigned char RevChar(unsigned char Byte)
{
typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));
What is the point of this assert?
tpname byte = (tpname)Byte;
What is the point of this typecast?
return (unsigned char)
(((byte & 128) >7)
| ((byte & 64) >5)
| ((byte & 32) >3)
| ((byte & 16) >1)
| ((byte & 8) << 1)
| ((byte & 4) << 3)
| ((byte & 2) << 5)
| ((byte & 1) << 7));
}

Yes... Yes... and ALL jeerer here,
can you overtake me on performance ?
Quite possibly. On many platforms, a lookup table can be much faster
(especially a small one that only needs 255 elements).
if you can, this is my homework.
BUT if you can't, it's just ur homework, okay ?

PS: donnot use TABLE plz.
Why not? What if the most optimal solution uses a table?

--
Clark S. Cox III
cl*******@gmail.com
Sep 4 '06 #20

P: n/a
Aman JIANG wrote:

<snip>
PS: donnot use TABLE plz.
That means I can't do it since all the computers here are on tables.
--
Flash Gordon
Sep 4 '06 #21

P: n/a
Aman JIANG posted:
Frederick Gotham wrote:
>The quantity of bits which comprises a byte is implementation-defined
and can be determined from the macro CHAR_BIT.

Even if 99.9999% of machines have 8-Bit bytes, that has no bearing
whatsover on the definition of the specification of the C Programming
Language.
Alright.
but i think u must make ur code work right first.

Be more specific -- your short, poorly spelled, poorly punctuated sentences
don't convey enough information for me to carry a discussion with you.

What do you mean by "make ur code work right first"? Your original code
doesn't work right; it malfunctions on any system where CHAR_BIT != 8.

If you start off writing your code assuming that CHAR_BIT == 8, then it won't
"work right first".

--

Frederick Gotham
Sep 4 '06 #22

P: n/a
Aman JIANG posted:
Eric Sosman wrote:
> Why not? Did your teacher forbid it?

1. I am NOT a Student. OK?

You come across as a student because of your poor writing skills.

2. TABLE is NOT a true algorithm for this.

In your own view perhaps. Plenty of algorithms use tables -- some of them
aren't even functions:

char unsigned const mirror[UCHAR_MAX] = {
/* Whatever */
};

int main()
{
char unsigned i;

/* Get input*/

/* Now print out mirror[i] */
}

--

Frederick Gotham
Sep 4 '06 #23

P: n/a
In article <11**********************@i3g2000cwc.googlegroups. com>,
Aman JIANG <Am*******@gmail.comwrote:
>2. TABLE is NOT a true algorithm for this.
You need a better definition of algorithm.

-- Richard

Sep 4 '06 #24

P: n/a
Frederick Gotham said:
Aman JIANG posted:
>Eric Sosman wrote:
>> Why not? Did your teacher forbid it?

1. I am NOT a Student. OK?


You come across as a student because of your poor writing skills.
(a) Some students have good writing skills, and others don't. Writing skill
is not a reliable indicator of studentinosity.
(b) The OP may not be a native English speaker. His or her *native* writing
skills may be far superior to yours or mine. We have no way of knowing.

<snip>

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 4 '06 #25

P: n/a
Aman JIANG wrote:
unsigned char RevChar(unsigned char Byte) {
typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));
tpname byte = (tpname)Byte;
return (unsigned char)
(((byte & 128) >7)
| ((byte & 64) >5)
| ((byte & 32) >3)
| ((byte & 16) >1)
| ((byte & 8) << 1)
| ((byte & 4) << 3)
| ((byte & 2) << 5)
| ((byte & 1) << 7));
}
Try this:

unsigned char RevChar (unsigned char b) {
b = ((b & 0x55u) << 1) | ((b & 0xaau) >1);
b = ((b & 0x33u) << 2) | ((b & 0xccu) >2);
b = ((b & 0x0fu) << 4) | ((b & 0xf0u) >4);
return b;
}
[...] can you overtake me on performance ?
;)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Sep 4 '06 #26

P: n/a
Richard Heathfield wrote:
Frederick Gotham said:
>>Aman JIANG posted:
>>>Eric Sosman wrote:
Why not? Did your teacher forbid it?
1. I am NOT a Student. OK?
You come across as a student because of your poor writing skills.

(a) Some students have good writing skills, and others don't. Writing skill
is not a reliable indicator of studentinosity.
Agreed.
(b) The OP may not be a native English speaker. His or her *native* writing
skills may be far superior to yours or mine. We have no way of knowing.
While possible, the use of slang shortcuts such as "ur" and "OK?" above
appear much more often with English-first-language posters, in my
experience.

--
Thad
Sep 4 '06 #27

P: n/a
Aman JIANG wrote:
hi man,
This is NOT my homework.
You're doing someone else homework by farming it
out to a thiurd party?

Just kidding; anyway, please try to include
context when you are replying, so that other
posters know what and who you are replying
to, much like the way I am replying to you.

--
goose
Have I offended you? Send flames to root@localhost
real email: lelanthran at gmail dot com
website : www.lelanthran.com
Sep 4 '06 #28

P: n/a
Clark S. Cox III wrote:
Quite possibly. On many platforms, a lookup table can be much faster
(especially a small one that only needs 255 elements).
Why not? What if the most optimal solution uses a table?
Because, this is a GAME only,
and the rule of this game is "real time".

if you use TABLE, you could gain the TIME, but you lose the SPACE.

Sep 5 '06 #29

P: n/a
Flash Gordon wrote:
That means I can't do it since all the computers here are on tables.
That's a good joke.

Sep 5 '06 #30

P: n/a
"Aman JIANG" <Am*******@gmail.comwrites:
Clark S. Cox III wrote:
>Quite possibly. On many platforms, a lookup table can be much faster
(especially a small one that only needs 255 elements).
>
Why not? What if the most optimal solution uses a table?

Because, this is a GAME only,
and the rule of this game is "real time".

if you use TABLE, you could gain the TIME, but you lose the SPACE.
You can't expect anyone to be interested in playing your little "game"
unless you've specified the rules *first*.

That doesn't imply that anyone is going to be interested even if you
do explain the rules.

What motivates this "game" of yours? What exactly is the point?
You've told us it isn't homework; what is it, then?

Finally, "real time" doesn't imply that you can't use a lookup table.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Sep 5 '06 #31

P: n/a
Frederick Gotham wrote:
Be more specific -- your short, poorly spelled, poorly punctuated sentences
don't convey enough information for me to carry a discussion with you.

What do you mean by "make ur code work right first"? Your original code
doesn't work right; it malfunctions on any system where CHAR_BIT != 8.

If you start off writing your code assuming that CHAR_BIT == 8, then it won't
"work right first".
Sorry.
My code that is just the 8-bits verison, it works on the IA-32 machines
only.
and i have other versions for other machines, too.

Sep 5 '06 #32

P: n/a
Clark S. Cox III wrote:
typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));

What is the point of this assert?
tpname byte = (tpname)Byte;

What is the point of this typecast?
This is just the IA-32 version, you can modify it.
And, on a IA-32 or mass, as a rule, a variable which
be a WORD is high-powered.

Sep 5 '06 #33

P: n/a
Richard Heathfield wrote:
(a) Some students have good writing skills, and others don't. Writing skill
is not a reliable indicator of studentinosity.
(b) The OP may not be a native English speaker. His or her *native* writing
skills may be far superior to yours or mine. We have no way of knowing.
Certainly, English is not my native writing :)

Sep 5 '06 #34

P: n/a
we******@gmail.com wrote:
Try this:

unsigned char RevChar (unsigned char b) {
b = ((b & 0x55u) << 1) | ((b & 0xaau) >1);
b = ((b & 0x33u) << 2) | ((b & 0xccu) >2);
b = ((b & 0x0fu) << 4) | ((b & 0xf0u) >4);
return b;
}
[...] can you overtake me on performance ?

;)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

exciting~
Now you are the kemp !!
This my test:

initialize...OK
times = 10000
buffersize = 768
testing...
.............................
Aman JIANG Okay.
RobinH00D Okay.
little_white Okay.
static_table(256) Okay.
reverse2 Okay.
reverse3 Okay.
reverse4 Okay.
static_table(16) Okay.
static_table(16)B Okay.
ZXX Okay.
Paul_Hsieh Okay.

sorting...OK
1 static_table(256) : 121958832 1
2 static_table(16)B : 125896128 1.03228
3 static_table(16) : 145015600 1.18905
4 Paul_Hsieh : 183532304 1.50487
5 Aman JIANG : 205804964 1.6875
6 RobinH00D : 231589744 1.89892
7 reverse3 : 288737236 2.3675
8 ZXX : 307013100 2.51735
9 reverse2 : 310884652 2.5491
10 little_white : 506653888 4.1543
11 reverse4 : 618891408 5.07459

Sep 5 '06 #35

P: n/a
Thad Smith wrote:
Richard Heathfield wrote:
<snip>
>(b) The OP may not be a native English speaker. His or her *native*
writing skills may be far superior to yours or mine. We have no way of
knowing.

While possible, the use of slang shortcuts such as "ur" and "OK?" above
appear much more often with English-first-language posters, in my
experience.
Having recently got back from India I can say that Indians use OK, cool
etc. and I saw printed material using thing like u and ur. It may be
that other countries where English is not the first language but
nevertheless is still common are going the same way.
--
Flash Gordon
Sep 5 '06 #36

P: n/a
Frederick Gotham <fg*******@SPAM.comwrote:
Aman JIANG posted:
Eric Sosman wrote:
Why not? Did your teacher forbid it?
1. I am NOT a Student. OK?

You come across as a student because of your poor writing skills.
No. He comes across as someone who has learnt English from web forums
and never could be arsed to learn better since, because of his poor
writing skills. He comes across as a student because he posts a homework
problem, even though he calls it a "GAME" (and what is it with those
capitals? Is homework more GAMEy than a normal game?).

Richard
Sep 5 '06 #37

P: n/a
Richard Bos said:

<snip>
He comes across as a student
No, he (or she) doesn't. Students study. The OP does not convey that
impression at all!

<snip>

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 5 '06 #38

P: n/a
Aman JIANG wrote:
we******@gmail.com wrote:
>Try this:

unsigned char RevChar (unsigned char b) {
b = ((b & 0x55u) << 1) | ((b & 0xaau) >1);
b = ((b & 0x33u) << 2) | ((b & 0xccu) >2);
b = ((b & 0x0fu) << 4) | ((b & 0xf0u) >4);
return b;
}
>>[...] can you overtake me on performance ?
;)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/


exciting~
Now you are the kemp !!
Since we've come this far: Google is your friend. Paul's trick is well-known.

http://graphics.stanford.edu/~seander/bithacks.html has many more of these.
Caution: most assume a particular size for integral types and none of these
hacks consider the possibility that an even faster implementation might use
assembly (which is not portable, but neither is assuming a fixed integer size).

S.
Sep 5 '06 #39

P: n/a

Aman JIANG wrote:
1 static_table(256) : 121958832 1
2 static_table(16)B : 125896128 1.03228
3 static_table(16) : 145015600 1.18905
4 Paul_Hsieh : 183532304 1.50487
5 Aman JIANG : 205804964 1.6875
6 RobinH00D : 231589744 1.89892
7 reverse3 : 288737236 2.3675
8 ZXX : 307013100 2.51735
9 reverse2 : 310884652 2.5491
10 little_white : 506653888 4.1543
11 reverse4 : 618891408 5.07459

These tests mean NOTHING. On a typical modern CPU, the results of
using a table lookup done in a loop will be very misleading. Table
lookup will *appear* to be faster if you call it in a loop, as the
table will stay in the CPU cache; but in a real-world program you'd
also be doing other things, like actually processing data. That data
flowing thru is very likely to push the table out of the cache, leading
to very slow table lookup times.

It would be a very strange program that reorders bits over and over
without haveing to process more than 64 to 256 of data (typical cache
sizes).

Sep 5 '06 #40

P: n/a
Richard Bos wrote:
No. He comes across as someone who has learnt English from web forums
and never could be arsed to learn better since, because of his poor
writing skills. He comes across as a student because he posts a homework
problem, even though he calls it a "GAME" (and what is it with those
capitals? Is homework more GAMEy than a normal game?).


"The pen is mightier than the sword."

Sorry, English is *not* my nature language. In fact, my english is bad.
To talk with all you here, i have to use english diffidently.
So, if you can understand me, Don't deride my writting, please.
I think that if i speak Chinese, you cannot understand me at all.

Again, "This Is Not My Homework", and, "I Am Not A Student".
To answer this question is easy for me, I can show you a lot
of answers.

This is just a inconspicuous game, if you hate it, i just want to say
"sorry".

*** Thank Paul Hsieh, you are praiseworthy.

thanks:)

Sep 5 '06 #41

P: n/a
Richard Tobin posted:
You need a better definition of algorithm.

The one I had at college was:

An algorithm is a finite set of well-defined instructions for
accomplishing a task.

--

Frederick Gotham
Sep 5 '06 #42

P: n/a

Aman JIANG wrote:
Clark S. Cox III wrote:
Quite possibly. On many platforms, a lookup table can be much faster
(especially a small one that only needs 255 elements).
>
Why not? What if the most optimal solution uses a table?

Because, this is a GAME only,
and the rule of this game is "real time".

if you use TABLE, you could gain the TIME, but you lose the SPACE.
Maybe, maybe not. The table is only 256 or so bytes. The table look
up
algorithm is very simple, the code for a more complicated algorithm
will
be longer (256 bytes longer? who knows). As well the longer
code may use code cache rather than data cache and code cache is
typically smaller. (Note, as pointed out elsethread, timing a lookup
table
in a tight loop may give misleading results).

Since any algorithm will need some "data" (e.g. the constants
indicating
bit positions) why not let the "data" be considered part of the
algorithm
and asign a limit to the total algorithm size? Except of course this
is completely non-portable. So what you could do is
put a limit on the total number of bytes used to express the
algorithm.

-William Hughes

Sep 5 '06 #43

P: n/a
"William Hughes" <wp*******@hotmail.comwrites:
Aman JIANG wrote:
>Clark S. Cox III wrote:
Quite possibly. On many platforms, a lookup table can be much faster
(especially a small one that only needs 255 elements).

Why not? What if the most optimal solution uses a table?

Because, this is a GAME only,
and the rule of this game is "real time".

if you use TABLE, you could gain the TIME, but you lose the SPACE.

Maybe, maybe not. The table is only 256 or so bytes. The
table look up algorithm is very simple, the code for a more
complicated algorithm will be longer (256 bytes longer? who
knows).
You could use a 16- or 8-byte table too. Code below not tested:

uint8_t
reverse_uint8 (uint8_t x)
{
static const uint8_t reverse_uint4[16]
= {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};

return reverse_uint4[x >4] | (reverse_uint4[x & 15] << 4);
}

It might still be faster than an approach without a table, and
certainly wouldn't be much bigger, if at all.
--
"The lusers I know are so clueless, that if they were dipped in clue
musk and dropped in the middle of pack of horny clues, on clue prom
night during clue happy hour, they still couldn't get a clue."
--Michael Girdwood, in the monastery
Sep 5 '06 #44

P: n/a
Aman JIANG wrote:
Clark S. Cox III wrote:
>> typedef unsigned long tpname;
assert(sizeof(tpname) == sizeof(void*));
What is the point of this assert?
>> tpname byte = (tpname)Byte;
What is the point of this typecast?

This is just the IA-32 version, you can modify it.
And, on a IA-32 or mass, as a rule, a variable which
be a WORD is high-powered.
Have you profiled that? I suspect that for code that simply reverses the
bits in a byte, there will be no noticeable speed difference.

You still haven't addressed the fact that the assert does not appear to
serve any purpose, and the cast is redundant.
--
Clark S. Cox III
cl*******@gmail.com
Sep 5 '06 #45

P: n/a
In article <11**********************@p79g2000cwp.googlegroups .com>,
Aman JIANG <Am*******@gmail.comwrote:
>Because, this is a GAME only,
and the rule of this game is "real time".
>if you use TABLE, you could gain the TIME, but you lose the SPACE.
Sounds like the TABLE accords with the rule of the GAME, then.

UNALTERED dissemination of this IMPORTANT information is ENCOURAGED.

-- Richard
Sep 5 '06 #46

P: n/a
Richard Tobin said:
In article <11**********************@p79g2000cwp.googlegroups .com>,
Aman JIANG <Am*******@gmail.comwrote:
>>Because, this is a GAME only,
and the rule of this game is "real time".
>>if you use TABLE, you could gain the TIME, but you lose the SPACE.

Sounds like the TABLE accords with the rule of the GAME, then.

UNALTERED dissemination of this IMPORTANT information is ENCOURAGED.
<shudderShades of Karl M </shudder>

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Sep 5 '06 #47

P: n/a
Aman JIANG wrote:
Richard Bos wrote:
>No. He comes across as someone who has learnt English from web
forums and never could be arsed to learn better since, because
of his poor writing skills. He comes across as a student because
he posts a homework problem, even though he calls it a "GAME"
(and what is it with those capitals? Is homework more GAMEy than
a normal game?).

"The pen is mightier than the sword."

Sorry, English is *not* my nature language. In fact, my english
is bad. To talk with all you here, i have to use english
diffidently. So, if you can understand me, Don't deride my
writting, please. I think that if i speak Chinese, you cannot
understand me at all.

Again, "This Is Not My Homework", and, "I Am Not A Student".
To answer this question is easy for me, I can show you a lot
of answers.
I think most here recognize the language difficulty, and will make
suitable allowances.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>
Sep 5 '06 #48

P: n/a
ri*****@cogsci.ed.ac.uk (Richard Tobin) wrote:
In article <11**********************@p79g2000cwp.googlegroups .com>,
Aman JIANG <Am*******@gmail.comwrote:
Because, this is a GAME only,
and the rule of this game is "real time".
if you use TABLE, you could gain the TIME, but you lose the SPACE.

Sounds like the TABLE accords with the rule of the GAME, then.

UNALTERED dissemination of this IMPORTANT information is ENCOURAGED.
The TABLE is not an ENTITY in and of itself.

Are you a CHAIR?

Richard, CABINET minister for silly walks
Sep 6 '06 #49

P: n/a
William Hughes wrote:
Maybe, maybe not. The table is only 256 or so bytes. The table look
up
algorithm is very simple, the code for a more complicated algorithm
will
be longer (256 bytes longer? who knows). As well the longer
code may use code cache rather than data cache and code cache is
typically smaller. (Note, as pointed out elsethread, timing a lookup
table
in a tight loop may give misleading results).

Since any algorithm will need some "data" (e.g. the constants
indicating
bit positions) why not let the "data" be considered part of the
algorithm
and asign a limit to the total algorithm size? Except of course this
is completely non-portable. So what you could do is
put a limit on the total number of bytes used to express the
algorithm.

-William Hughes
Yes. If this question is not for the "8-bit byte", it's for 32-bit or
64-bit
unsigned integer, i think that nobody could use a TABLE.

Sep 6 '06 #50

77 Replies

This discussion thread is closed

Replies have been disabled for this discussion.