Bit Reversal using recursion

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

  1. Krypto

    Krypto Guest

    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
    #1
    1. Advertising

  2. Krypto

    Krypto Guest

    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
    #2
    1. Advertising

  3. Krypto

    Mark Bluemel Guest

    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);
    Mark Bluemel, Nov 1, 2007
    #3
  4. Krypto

    pete Guest

    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;
    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
    pete, Nov 1, 2007
    #4
  5. Krypto

    Krypto Guest

    > 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.
    Krypto, Nov 1, 2007
    #5
  6. Krypto

    Richard Guest

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

    Richard Guest

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

    pete Guest

    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
    pete, Nov 1, 2007
    #8
  9. "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
    #9
  10. "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
    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.
    Charlie Gordon, Nov 7, 2007
    #10
  11. Krypto

    Keith Willis Guest

    Keith Willis, Nov 7, 2007
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Michael
    Replies:
    74
    Views:
    1,658
    Dhruv
    Dec 24, 2003
  2. M. Norton

    Bit reversal and IRC

    M. Norton, May 11, 2006, in forum: VHDL
    Replies:
    11
    Views:
    3,008
    Mike Treseler
    May 12, 2006
  3. Sathyaish

    in-place string reversal

    Sathyaish, Mar 28, 2006, in forum: Python
    Replies:
    12
    Views:
    754
    Felipe Almeida Lessa
    Mar 28, 2006
  4. Replies:
    6
    Views:
    343
    Robert Bachmann
    Mar 17, 2005
  5. Replies:
    8
    Views:
    716
    John Reye
    Apr 26, 2012
Loading...

Share This Page