reverse bit order

Discussion in 'C++' started by mike7411@gmail.com, Oct 9, 2006.

  1. Guest

    Is there any easy way to reverse the order of the bits in a byte in
    C++?

    (i.e. 00000001 becomes 10000000)
     
    , Oct 9, 2006
    #1
    1. Advertising

  2. wrote:
    > Is there any easy way to reverse the order of the bits in a byte in
    > C++?
    >
    > (i.e. 00000001 becomes 10000000)


    http://www.google.com/search?hl=en&q=reverse bits byte

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Oct 9, 2006
    #2
    1. Advertising

  3. Martin Steen Guest

    wrote:
    > Is there any easy way to reverse the order of the bits in a byte in
    > C++?
    >
    > (i.e. 00000001 becomes 10000000)
    >


    No. There is only the hard way ;)
    You have to shift the bits one by one.
    The best idea is to calculate an array
    of 256 values that contain the reversed bits.
    Then you can "look up" in that array. Here
    is the code to make the array (named "BitField"):

    int BitField[256];
    for (int i = 0; i < 256; i++)
    {
    int k = i;
    BitField = 0;
    for (int b = 0; b < 8; b++)
    {
    BitField <<= 1;
    BitField |= k & 1;
    k >>= 1;
    }
    }

    If you want safer code, use a vector instead of an array:
    vector<int> BitField(256);

    Best regards, Martin

    P.S. normally, I don't do other people's homework - SCNR this time ;)
     
    Martin Steen, Oct 10, 2006
    #3
  4. Frederick Gotham, Oct 10, 2006
    #4
  5. Pete Becker Guest

    Martin Steen wrote:
    >
    > int BitField[256];
    > for (int i = 0; i < 256; i++)
    > {
    > int k = i;
    > BitField = 0;
    > for (int b = 0; b < 8; b++)
    > {
    > BitField <<= 1;
    > BitField |= k & 1;
    > k >>= 1;
    > }
    > }
    >
    > If you want safer code, use a vector instead of an array:
    > vector<int> BitField(256);
    >


    How is that safer? Either way looks equally correct. If you're worried
    about typos, it's far better to use a manifest constant instead of that
    hardcoded value of 256.

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." For more information about this book, see
    www.petebecker.com/tr1book.
     
    Pete Becker, Oct 10, 2006
    #5
  6. Martin Steen wrote:
    > wrote:
    >> Is there any easy way to reverse the order of the bits in a byte in
    >> C++?
    >>
    >> (i.e. 00000001 becomes 10000000)
    >>

    >
    > No. There is only the hard way ;)


    If there are only 8 bits in a byte (and nobody said it was the actual
    requirement), then a table of 255 values would be the easiest way.

    if (mybyte)
    mybyte = mytable[mybyte];

    Now, generation of the table can be done once, outside of your program.

    > [..code not involving a table redacted..]


    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Oct 10, 2006
    #6
  7. Pete Becker Guest

    wrote:
    > Is there any easy way to reverse the order of the bits in a byte in
    > C++?
    >
    > (i.e. 00000001 becomes 10000000)
    >


    The one true way is to recognize that reversing any sequence of bits
    involves only splitting it into two parts and returning a value whose
    upper half is the reverse of the original lower half and whose lower
    half is the reverse of the original upper half. Like this:

    #include <limits>
    #include <iomanip>
    #include <iostream>
    using std::numeric_limits;
    using std::cout; using std::hex; using std::showbase;
    using std::internal; using std::setw;

    template <unsigned n> struct reverser_imp
    {
    static inline unsigned reverse(unsigned val, unsigned mask)
    {
    mask >>= (n/2);
    return reverser_imp<n/2>::reverse((val >> (n/2)) & mask, mask)
    | (reverser_imp<n/2>::reverse(val & mask, mask) << (n/2));
    }
    };

    template <> struct reverser_imp<1>
    {
    static inline unsigned reverse(unsigned val, unsigned)
    {
    return val;
    }
    };

    inline unsigned reverse(unsigned val)
    {
    return reverser_imp<numeric_limits<unsigned char>::digits>::
    reverse(val, numeric_limits<unsigned char>::max());
    }

    void show_reversed(unsigned val)
    {
    cout.fill('0');
    cout << hex << showbase << internal;
    cout << setw(4) << val << ": "
    << setw(4) << reverse(val) << '\n';
    }


    int main()
    {
    show_reversed(0x0f);
    show_reversed(0x80);
    show_reversed(0x40);
    show_reversed(0xC0);
    return 0;
    }


    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." For more information about this book, see
    www.petebecker.com/tr1book.
     
    Pete Becker, Oct 10, 2006
    #7
  8. Pete Becker posted:

    > inline unsigned reverse(unsigned val)
    > {
    > return reverser_imp<numeric_limits<unsigned char>::digits>::
    > reverse(val, numeric_limits<unsigned char>::max());
    > }



    In my opinion, it's major overkill to use either of:

    numeric_limits<char unsigned>::digits
    numeric_limits<char unsigned>::max

    The former can be retrieved from:

    CHAR_BIT

    , while the latter can be retrieved from:

    (char unsigned)-1

    or even:

    UCHAR_MAX

    --

    Frederick Gotham
     
    Frederick Gotham, Oct 10, 2006
    #8
  9. Pete Becker Guest

    Frederick Gotham wrote:
    > Pete Becker posted:
    >
    >> inline unsigned reverse(unsigned val)
    >> {
    >> return reverser_imp<numeric_limits<unsigned char>::digits>::
    >> reverse(val, numeric_limits<unsigned char>::max());
    >> }

    >
    >
    > In my opinion, it's major overkill to use either of:
    >
    > numeric_limits<char unsigned>::digits
    > numeric_limits<char unsigned>::max
    >
    > The former can be retrieved from:
    >
    > CHAR_BIT
    >
    > , while the latter can be retrieved from:
    >
    > (char unsigned)-1
    >
    > or even:
    >
    > UCHAR_MAX
    >


    Haven't you gotten the word? Macros are evil. This is the 21st century.
    Quaint C approaches should never be used. Templates, templates,
    templates. Always.

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." For more information about this book, see
    www.petebecker.com/tr1book.
     
    Pete Becker, Oct 10, 2006
    #9
  10. Pete Becker posted:

    > Haven't you gotten the word? Macros are evil. This is the 21st century.
    > Quaint C approaches should never be used. Templates, templates,
    > templates. Always.


    Exceptions, exceptions, exception -- and not the kind you throw!

    C++ has many "warts" (if you wish to call them that) which perpetuate from
    its origins in C. We have accepted these warts, documented them, and moved
    forward.

    When you want to give something a name in C++ (be it a function, an object,
    a class), then you don't need to pick a very unique name, because all you
    need do is enclose it in a namespace:

    namespace MyNamespace { int cout; }

    Macros muck this up completely. However, there is a finite list of macros
    which the Standard defines, such as:

    INT_MAX
    UCHAR_MAX
    CHAR_BIT

    As always, the Standard can take liberties wherever it pleases, and it
    chooses to define these macros. If you genuinely perfer the numeric_limits
    method, then go ahead. However, I myself find it awfully tedious and
    longwinded, and I prefer good ol' CHAR_BIT.

    While one should hesitate to define macros (for the obvious reasons),
    there's no need to hesitate to use the ones that are already there, and
    which will _always_ be there. Never will we be able to write:

    int CHAR_BIT = 5;

    Also, you might notice that "max" and "min" don't evaluate to a compile-
    time constant, which make INT_MAX and the like all the more attractive.

    --

    Frederick Gotham
     
    Frederick Gotham, Oct 10, 2006
    #10
  11. Pete Becker Guest

    Frederick Gotham wrote:
    >
    > Macros muck this up completely.


    Yup. They're evil. Doesn't matter how you rationalize it.

    [rationalizaton snipped]

    It's far better to write long winded, unmaintainable, compiler-busting
    templates than to resort to macros. That's the C++ way!

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." For more information about this book, see
    www.petebecker.com/tr1book.
     
    Pete Becker, Oct 10, 2006
    #11
  12. Pete Becker posted:

    > Frederick Gotham wrote:
    >>
    >> Macros muck this up completely.

    >
    > Yup. They're evil. Doesn't matter how you rationalize it.
    >
    > [rationalizaton snipped]



    So _your_ rationalisation is this:

    There's a undamaged wheel in a car-wreck, but we can't make use of it
    because it's evil for a car to crash.


    > It's far better to write long winded, unmaintainable, compiler-busting
    > templates than to resort to macros. That's the C++ way!



    Indeed it is, but not when it comes to the most basic of things, and there
    is little more basic than the CHAR_BIT family of macros. Even if you choose
    to never us CHAR_BIT and the like, you'll never be able to write:

    namespace MyNamespace { int CHAR_BIT(); }

    well... not in your header files in anyway.

    --

    Frederick Gotham
     
    Frederick Gotham, Oct 10, 2006
    #12
  13. Pete Becker Guest

    Frederick Gotham wrote:
    > Pete Becker posted:
    >
    >
    >> It's far better to write long winded, unmaintainable, compiler-busting
    >> templates than to resort to macros. That's the C++ way!

    >
    >
    > Indeed it is,


    Now you've seen the light.

    > but not when it comes to the most basic of things, and there
    > is little more basic than the CHAR_BIT family of macros. Even if you choose
    > to never us CHAR_BIT and the like, you'll never be able to write:
    >
    > namespace MyNamespace { int CHAR_BIT(); }
    >
    > well... not in your header files in anyway.
    >


    That's because macros are evil. Always use templates. Never use macros.
    If you can't write it as a template you haven't tried hard enough.

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." For more information about this book, see
    www.petebecker.com/tr1book.
     
    Pete Becker, Oct 10, 2006
    #13
  14. Pete Becker posted:

    > That's because macros are evil. Always use templates. Never use macros.
    > If you can't write it as a template you haven't tried hard enough.



    This has nothing to do with "Writing Templates" Vs "Writing Macros", and
    everything to do with the Standard Library, which provides certain macros.

    There's plenty of things you can do with macros which you _can't_ do with
    templates.

    --

    Frederick Gotham
     
    Frederick Gotham, Oct 10, 2006
    #14
  15. Frederick Gotham wrote:

    > Pete Becker posted:
    >
    > > That's because macros are evil. Always use templates. Never use macros.
    > > If you can't write it as a template you haven't tried hard enough.

    >
    >
    > This has nothing to do with "Writing Templates" Vs "Writing Macros", and
    > everything to do with the Standard Library, which provides certain macros.
    >
    > There's plenty of things you can do with macros which you _can't_ do with
    > templates.


    Hey Fred, so that the rest of us can sleep easy, could you please post
    something acknowledging that you knew that each of Pete's postings in
    this subthread regarding templates vs. macros has been tongue-in-cheek.
    Your responses have appeared to take Pete seriously, and perhaps you
    have done so just to be funny, but if so I must confess that your humor
    is sometimes over my head.

    Best regards,

    Tom
     
    Thomas Tutone, Oct 10, 2006
    #15
  16. Thomas Tutone posted:

    > Hey Fred, so that the rest of us can sleep easy, could you please post
    > something acknowledging that you knew that each of Pete's postings in
    > this subthread regarding templates vs. macros has been tongue-in-cheek.
    > Your responses have appeared to take Pete seriously, and perhaps you
    > have done so just to be funny, but if so I must confess that your humor
    > is sometimes over my head.



    I had no reason to think Pete was being sarcastic.

    Maybe I'm a bit socially retarded today. . . or maybe I'm just used to the
    wide variety of people (and therefore attitudes) I encounter on Usenet.

    --

    Frederick Gotham
     
    Frederick Gotham, Oct 10, 2006
    #16
  17. Pete Becker Guest

    Frederick Gotham wrote:
    > Pete Becker posted:
    >
    >> That's because macros are evil. Always use templates. Never use macros.
    >> If you can't write it as a template you haven't tried hard enough.

    >
    >
    > This has nothing to do with "Writing Templates" Vs "Writing Macros", and
    > everything to do with the Standard Library, which provides certain macros.


    It's about writing code to reverse the bits in a byte. Don't you remember?

    >
    > There's plenty of things you can do with macros which you _can't_ do with
    > templates.
    >


    If you can't do it with templates you shouldn't be doing it.

    --

    -- Pete

    Author of "The Standard C++ Library Extensions: a Tutorial and
    Reference." For more information about this book, see
    www.petebecker.com/tr1book.
     
    Pete Becker, Oct 10, 2006
    #17
  18. Jim Langston Guest

    "Pete Becker" <> wrote in message
    news:...
    > Frederick Gotham wrote:
    >> Pete Becker posted:
    >>
    >>
    >>> It's far better to write long winded, unmaintainable, compiler-busting
    >>> templates than to resort to macros. That's the C++ way!

    >>
    >>
    >> Indeed it is,

    >
    > Now you've seen the light.
    >
    >> but not when it comes to the most basic of things, and there is little
    >> more basic than the CHAR_BIT family of macros. Even if you choose to
    >> never us CHAR_BIT and the like, you'll never be able to write:
    >>
    >> namespace MyNamespace { int CHAR_BIT(); }
    >>
    >> well... not in your header files in anyway.
    >>

    >
    > That's because macros are evil. Always use templates. Never use macros. If
    > you can't write it as a template you haven't tried hard enough.


    So tell me, do you use header guards?
     
    Jim Langston, Oct 10, 2006
    #18
  19. Nate Barney Guest

    Frederick Gotham wrote:
    > While one should hesitate to define macros (for the obvious reasons),
    > there's no need to hesitate to use the ones that are already there, and
    > which will _always_ be there. Never will we be able to write:
    >
    > int CHAR_BIT = 5;


    what about:

    #undef CHAR_BIT
    int CHAR_BIT = 5;

    or is that Undefined Behavior?

    Nate
     
    Nate Barney, Oct 10, 2006
    #19
  20. Guest

    Nate Barney wrote:
    > Frederick Gotham wrote:
    > > While one should hesitate to define macros (for the obvious reasons),
    > > there's no need to hesitate to use the ones that are already there, and
    > > which will _always_ be there. Never will we be able to write:
    > >
    > > int CHAR_BIT = 5;

    >
    > what about:
    >
    > #undef CHAR_BIT
    > int CHAR_BIT = 5;
    >
    > or is that Undefined Behavior?
    >


    Hahaha... it never stops, does it? :)
     
    , Oct 10, 2006
    #20
    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. dogbite
    Replies:
    4
    Views:
    701
    osmium
    Oct 10, 2003
  2. Replies:
    9
    Views:
    1,009
    Juha Nieminen
    Aug 22, 2007
  3. imageguy
    Replies:
    9
    Views:
    462
    John Machin
    Jan 3, 2009
  4. Mike -- Email Ignored

    Bit Order in Bit Fields

    Mike -- Email Ignored, May 2, 2009, in forum: C++
    Replies:
    0
    Views:
    389
    Mike -- Email Ignored
    May 2, 2009
  5. Luis Cupido

    SLV reverse bit order

    Luis Cupido, Oct 17, 2012, in forum: VHDL
    Replies:
    8
    Views:
    666
    HT-Lab
    Nov 2, 2012
Loading...

Share This Page