Bit Reversal using recursion

[Krypto]

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]

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

 

[Mark Bluemel]

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

 

[pete]

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

 

[Krypto]

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.

 

[Richard]

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]

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.

 

[pete]

Set Most Significant unsigned char Bit in hi_mask.

Set Least Significant Bit in lo_mask.

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.

 

[Charlie Gordon]

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]

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

 

[Keith Willis]

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

What an amazingly useful site! Thanks for the pointer.