# Bit Reversal using recursion

Discussion in 'C Programming' started by Krypto, Nov 1, 2007.

1. ### KryptoGuest

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 ?

Krypto, Nov 1, 2007

2. ### KryptoGuest

On Nov 1, 12:09 pm, 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.
>
> 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;
}

Krypto, Nov 1, 2007

3. ### Mark BluemelGuest

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

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);

Mark Bluemel, Nov 1, 2007
4. ### peteGuest

Krypto wrote:
>
> On Nov 1, 12:09 pm, 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.
> >
> > 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;

do {
}
return byte;
}

--
pete

pete, Nov 1, 2007
5. ### KryptoGuest

> 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;
>
> do {
> }
> return byte;
>
> }

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

Krypto, Nov 1, 2007
6. ### RichardGuest

Mark Bluemel <> 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 ...

Richard, Nov 1, 2007
7. ### RichardGuest

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

Richard, Nov 1, 2007
8. ### peteGuest

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 either the MSB bit or the LSB,
but not both, are set in byte,

then flip them.

> > }

Repeat for next highest and lowest bits, until done.

> > return byte;
> >
> > }

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

--
pete

pete, Nov 1, 2007
9. ### Charlie GordonGuest

"Richard" <> a écrit dans le message de news:
...
> Krypto <> 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.
>

Charlie Gordon, Nov 7, 2007
10. ### Charlie GordonGuest

"Richard" <> a écrit dans le message de news:
...
> Krypto <> 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
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.

Charlie Gordon, Nov 7, 2007
11. ### Keith WillisGuest

Keith Willis, Nov 7, 2007