Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Bit Reversal using recursion

Reply
Thread Tools

Bit Reversal using recursion

 
 
Krypto
Guest
Posts: n/a
 
      11-01-2007
Hi,

This is the problem of reversing a number from 10110110 to 01101101. I
am wanting to reverse bits in an a byte, i.e. 8 bit.

I have already went through some old posts about bit reversal. I was
trying to approach this problem from a different perspective and
thought of the following two solutions.

1. Using Bit fields. If we can swap MSB to LSB and subsequently
internal bits.
2. Using masking and recursion. First swap left and right partition.
Then swap internally like quick sort.


The previous solutions that were proposed were to do a look up using a
table and it was told that it was the fastest means of doing it. I
could not properly understand that solution as to how to create a look
up table and look up. Can somebody please explain it.


Can you (experienced) folks comments on my approach or what other
approach would be better for this problem ?

 
Reply With Quote
 
 
 
 
Krypto
Guest
Posts: n/a
 
      11-01-2007
On Nov 1, 12:09 pm, Krypto <(E-Mail Removed)> wrote:
> Hi,
>
> This is the problem of reversing a number from 10110110 to 01101101. I
> am wanting to reverse bits in an a byte, i.e. 8 bit.
>
> I have already went through some old posts about bit reversal. I was
> trying to approach this problem from a different perspective and
> thought of the following two solutions.
>
> 1. Using Bit fields. If we can swap MSB to LSB and subsequently
> internal bits.
> 2. Using masking and recursion. First swap left and right partition.
> Then swap internally like quick sort.
>
> The previous solutions that were proposed were to do a look up using a
> table and it was told that it was the fastest means of doing it. I
> could not properly understand that solution as to how to create a look
> up table and look up. Can somebody please explain it.
>
> Can you (experienced) folks comments on my approach or what other
> approach would be better for this problem ?


I forgot to attach my attempt using masking and iterating. I want to
discuss an alternate way to solve the problem and want to know more
about it. And it is not my homework.

char reverse_order_of_bits(char num)
{
char result = 0;
while(num)
{
char temp = num & 0x1; // obtaining LSB from num
num = num >> 1; // shifting num to right bit by bit
result = result | temp; // building result by using bits
obtained from num
result = result << 1; // shifting result to left bit by bit
}
return result;
}

 
Reply With Quote
 
 
 
 
Mark Bluemel
Guest
Posts: n/a
 
      11-01-2007
Krypto wrote:
> Hi,
>
> This is the problem of reversing a number from 10110110 to 01101101. I
> am wanting to reverse bits in an a byte, i.e. 8 bit.


Why?

> I have already went through some old posts about bit reversal. I was
> trying to approach this problem from a different perspective and
> thought of the following two solutions.
> 1. Using Bit fields. If we can swap MSB to LSB and subsequently
> internal bits.
> 2. Using masking and recursion. First swap left and right partition.
> Then swap internally like quick sort.
>
>
> The previous solutions that were proposed were to do a look up using a
> table and it was told that it was the fastest means of doing it. I
> could not properly understand that solution as to how to create a look
> up table and look up. Can somebody please explain it.


An eight-bit byte can have up to 256 distinct values. Simply create a
256-element array containing their reversed values... (Usually done by
copying an existing version...)

> Can you (experienced) folks comments on my approach or what other
> approach would be better for this problem ?
>

This is discussed so often in clc that perhaps you could search Google
groups for an old discussion.

You could also do some normal Google searches and get to (for example)
http://graphics.stanford.edu/~seander/bithacks.html

I rather like this version (untested hack of the 32-bit version in the
above link) :-

unsigned char v; /* 8 bit byte to reverse bit order */
/* note that bytes don't have to be 8-bit
* but we'll assume that for this example
*/

/* swap odd and even bits */
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
/* swap consecutive pairs */
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
/* swap nybbles ... */
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      11-01-2007
Krypto wrote:
>
> On Nov 1, 12:09 pm, Krypto <(E-Mail Removed)> wrote:
> > Hi,
> >
> > This is the problem of reversing a number from 10110110 to 01101101. I
> > am wanting to reverse bits in an a byte, i.e. 8 bit.
> >
> > I have already went through some old posts about bit reversal. I was
> > trying to approach this problem from a different perspective and
> > thought of the following two solutions.
> >
> > 1. Using Bit fields. If we can swap MSB to LSB and subsequently
> > internal bits.
> > 2. Using masking and recursion. First swap left and right partition.
> > Then swap internally like quick sort.
> >
> > The previous solutions that were proposed were to do a look up using a
> > table and it was told that it was the fastest means of doing it. I
> > could not properly understand that solution as to how to create a look
> > up table and look up. Can somebody please explain it.
> >
> > Can you (experienced) folks comments on my approach or what other
> > approach would be better for this problem ?

>
> I forgot to attach my attempt using masking and iterating. I want to
> discuss an alternate way to solve the problem and want to know more
> about it. And it is not my homework.
>
> char reverse_order_of_bits(char num)
> {
> char result = 0;
> while(num)
> {
> char temp = num & 0x1; // obtaining LSB from num
> num = num >> 1; // shifting num to right bit by bit
> result = result | temp; // building result by using bits
> obtained from num
> result = result << 1; // shifting result to left bit by bit
> }
> return result;
> }


new.c crashes my machine.

/* BEGIN new.c */

#include <limits.h>

char reverse_order_of_bits(char num);

int main(void)
{
char rev;

rev = reverse_order_of_bits(CHAR_MIN);
return 0;
}

char reverse_order_of_bits(char num)
{
char result = 0;
while(num)
{
char temp = num & 0x1; // obtaining LSB from num
num = num >> 1; // shifting num to right bit by bit
result = result | temp; // building result by using bits obtained
from num
result = result << 1; // shifting result to left bit by bit
}
return result;
}

/* END new.c */

unsigned char is better for working with raw memory bytes.

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

--
pete
 
Reply With Quote
 
Krypto
Guest
Posts: n/a
 
      11-01-2007
> unsigned char is better for working with raw memory bytes.
>
> unsigned char bit_rev(unsigned char byte)
> {
> unsigned hi_mask = ((unsigned char)-1 >> 1) + 1;
> unsigned 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;
>
> }


Can you tell exactly what is happening in your code ? I could not get
the logic right.


 
Reply With Quote
 
Richard
Guest
Posts: n/a
 
      11-01-2007
Mark Bluemel <(E-Mail Removed)> writes:

> Krypto wrote:
>> Hi,
>>
>> This is the problem of reversing a number from 10110110 to 01101101. I
>> am wanting to reverse bits in an a byte, i.e. 8 bit.

>
> Why?
>
>> I have already went through some old posts about bit reversal. I was
>> trying to approach this problem from a different perspective and
>> thought of the following two solutions.
>> 1. Using Bit fields. If we can swap MSB to LSB and subsequently
>> internal bits.
>> 2. Using masking and recursion. First swap left and right partition.
>> Then swap internally like quick sort.
>>
>>
>> The previous solutions that were proposed were to do a look up using a
>> table and it was told that it was the fastest means of doing it. I
>> could not properly understand that solution as to how to create a look
>> up table and look up. Can somebody please explain it.

>
> An eight-bit byte can have up to 256 distinct values. Simply create a
> 256-element array containing their reversed values... (Usually done by
> copying an existing version...)


Why would you copy an existing one? Just use the existing one ...
 
Reply With Quote
 
Richard
Guest
Posts: n/a
 
      11-01-2007
Krypto <(E-Mail Removed)> writes:

> Hi,
>
> This is the problem of reversing a number from 10110110 to 01101101. I
> am wanting to reverse bits in an a byte, i.e. 8 bit.
>
> I have already went through some old posts about bit reversal. I was
> trying to approach this problem from a different perspective and
> thought of the following two solutions.
>
> 1. Using Bit fields. If we can swap MSB to LSB and subsequently
> internal bits.
> 2. Using masking and recursion. First swap left and right partition.
> Then swap internally like quick sort.
>
>
> The previous solutions that were proposed were to do a look up using a
> table and it was told that it was the fastest means of doing it. I
> could not properly understand that solution as to how to create a look
> up table and look up. Can somebody please explain it.
>
>
> Can you (experienced) folks comments on my approach or what other
> approach would be better for this problem ?


http://www.c.happycodings.com/Miscellaneous/code28.html

,----
| #include <stdio.h>
|
| static unsigned long reverse(unsigned long x) {
| unsigned long h = 0;
| int i = 0;
|
| for(h = i = 0; i < 32; i++) {
| h = (h << 1) + (x & 1);
| x >>= 1;
| }
|
| return h;
| }
`----

Clearly there are things to fiddle with for the types you are interested
in.

This site can help with a lot of trivial utilities.

 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      11-01-2007
Krypto wrote:
>
> > unsigned char is better for working with raw memory bytes.
> >
> > unsigned char bit_rev(unsigned char byte)
> > {
> > unsigned hi_mask = ((unsigned char)-1 >> 1) + 1;


Set Most Significant unsigned char Bit in hi_mask.

> > unsigned lo_mask = 1;


Set Least Significant Bit in lo_mask.

> >
> > do {
> > if (!(byte & hi_mask) != !(byte & lo_mask)) {


If either the MSB bit or the LSB,
but not both, are set in byte,

> > byte ^= hi_mask | lo_mask;


then flip them.

> > }
> > hi_mask >>= 1;
> > lo_mask <<= 1;


Repeat for next highest and lowest bits, until done.

> > } while (hi_mask > lo_mask);
> > return byte;
> >
> > }

>
> Can you tell exactly what is happening in your code ? I could not get
> the logic right.


--
pete
 
Reply With Quote
 
Charlie Gordon
Guest
Posts: n/a
 
      11-07-2007
"Richard" <(E-Mail Removed)> a écrit dans le message de news:
http://www.velocityreviews.com/forums/(E-Mail Removed)...
> Krypto <(E-Mail Removed)> writes:
>
>> Hi,
>>
>> This is the problem of reversing a number from 10110110 to 01101101. I
>> am wanting to reverse bits in an a byte, i.e. 8 bit.
>>
>> I have already went through some old posts about bit reversal. I was
>> trying to approach this problem from a different perspective and
>> thought of the following two solutions.
>>
>> 1. Using Bit fields. If we can swap MSB to LSB and subsequently
>> internal bits.
>> 2. Using masking and recursion. First swap left and right partition.
>> Then swap internally like quick sort.
>>
>>
>> The previous solutions that were proposed were to do a look up using a
>> table and it was told that it was the fastest means of doing it. I
>> could not properly understand that solution as to how to create a look
>> up table and look up. Can somebody please explain it.
>>
>>
>> Can you (experienced) folks comments on my approach or what other
>> approach would be better for this problem ?

>
> http://www.c.happycodings.com/Miscellaneous/code28.html
>
> ,----
> | #include <stdio.h>
> |
> | static unsigned long reverse(unsigned long x) {
> | unsigned long h = 0;
> | int i = 0;
> |
> | for(h = i = 0; i < 32; i++) {
> | h = (h << 1) + (x & 1);
> | x >>= 1;
> | }
> |
> | return h;
> | }
> `----
>
> Clearly there are things to fiddle with for the types you are interested
> in.
>
> This site can help with a lot of trivial utilities.
>



 
Reply With Quote
 
Charlie Gordon
Guest
Posts: n/a
 
      11-07-2007
"Richard" <(E-Mail Removed)> a écrit dans le message de news:
(E-Mail Removed)...
> Krypto <(E-Mail Removed)> writes:
>
>> Hi,
>>
>> This is the problem of reversing a number from 10110110 to 01101101. I
>> am wanting to reverse bits in an a byte, i.e. 8 bit.
>>
>> I have already went through some old posts about bit reversal. I was
>> trying to approach this problem from a different perspective and
>> thought of the following two solutions.
>>
>> 1. Using Bit fields. If we can swap MSB to LSB and subsequently
>> internal bits.
>> 2. Using masking and recursion. First swap left and right partition.
>> Then swap internally like quick sort.
>>
>>
>> The previous solutions that were proposed were to do a look up using a
>> table and it was told that it was the fastest means of doing it. I
>> could not properly understand that solution as to how to create a look
>> up table and look up. Can somebody please explain it.
>>
>>
>> Can you (experienced) folks comments on my approach or what other
>> approach would be better for this problem ?

>
> http://www.c.happycodings.com/Miscellaneous/code28.html


This site is a real pain. Trying to find useful code in the middle of heavy
marketing bullshit, dozens of google adds and fake menus is not workable.
And the code sniplets are not even syntax colored. And the programming
style is not appealing either. Not to mention bugs... Yuk!

> ,----
> | #include <stdio.h>
> |
> | static unsigned long reverse(unsigned long x) {
> | unsigned long h = 0;
> | int i = 0;
> |
> | for(h = i = 0; i < 32; i++) {
> | h = (h << 1) + (x & 1);
> | x >>= 1;
> | }
> |
> | return h;
> | }
> `----


not all unsigned longs are 32 bit wide.
CHAR_BIT * sizeof(unsigned long) would be better, but not strictly correct
either.

> Clearly there are things to fiddle with for the types you are interested
> in.
>
> This site can help with a lot of trivial utilities.


Not as good as Sean Andersons bit twiddling hacks:
http://graphics.stanford.edu/~seander/bithacks.html

--
Chqrlie.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
va_arg... recursion: changing arguments and the using recursion jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM
What is the point of having 16 bit colour if a computer monitor can only display 8 bit colour? How do you edit 16 bit colour when you can only see 8 bit? Scotius Digital Photography 6 07-13-2010 03:33 AM
Bit reversal and IRC M. Norton VHDL 11 05-12-2006 08:20 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit, Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new ! vvcd Computer Support 0 09-17-2004 08:15 PM
64 bit - Windows Liberty 64bit, Windows Limited Edition 64 Bit,Microsoft SQL Server 2000 Developer Edition 64 Bit, IBM DB2 64 bit - new! Ionizer Computer Support 1 01-01-2004 07:27 PM



Advertisments