Shifting bits

Discussion in 'C Programming' started by jacob navia, Oct 27, 2009.

  1. jacob navia

    jacob navia Guest

    Given a bitstring of size siz (in bytes), shift it right by 1 bit.
    Return the bit that was shifted out

    static int Shift(char *p,size_t siz)
    {
    int carry;
    size_t i;

    carry = p[0]&1;
    p[0] >>= 1;
    for (i=1; i<siz;i++) {
    int s = p&1;
    p = (p >> 1) | (carry << 7);
    if (i < siz-1)
    carry = p[i+1]&1;
    else carry = s;
    }
    return carry;
    }

    Somehow it doesn't look very well. I am sure that there is a better solution.

    Any takers?

    jacob
    jacob navia, Oct 27, 2009
    #1
    1. Advertising

  2. jacob navia

    Alan Curry Guest

    In article <hc7o05$eil$>, jacob navia <> wrote:
    >Given a bitstring of size siz (in bytes), shift it right by 1 bit.
    >Return the bit that was shifted out
    >
    >static int Shift(char *p,size_t siz)
    >{
    > int carry;
    > size_t i;
    >
    > carry = p[0]&1;
    > p[0] >>= 1;
    > for (i=1; i<siz;i++) {
    > int s = p&1;
    > p = (p >> 1) | (carry << 7);
    > if (i < siz-1)
    > carry = p[i+1]&1;
    > else carry = s;
    > }
    > return carry;
    >}
    >
    >Somehow it doesn't look very well. I am sure that there is a better solution.


    Have you tested it? If that produces the result you wanted I'd like to see
    your test case. It failed mine.

    Here's the test case I used, together with my working implementation. The key
    idea is to set the "carry" variable to be the value that will be shifted into
    the top bit of the next byte. Set that to 0 before the loop starts, and you
    don't have to special-case the first byte.

    #include <stdio.h>
    #include <limits.h>

    static int Shift(char *p,size_t siz)
    {
    size_t i;
    int carry;

    carry = 0;
    for(i=0 ; i<siz ; ++i) {
    int s = p & 1;
    p = (p>>1) | (carry<<(CHAR_BIT-1));
    carry = s;
    }
    return carry;
    }

    int main(void)
    {
    char testdat[8] = "\xfe\xed\xfa\xce\xde\xad\xbe\xef";
    size_t i;
    int bit;

    for(i=0 ; i < sizeof(testdat)*CHAR_BIT ; ++i) {
    bit = Shift(testdat, sizeof(testdat));
    printf("Got bit %d\n", bit);
    }

    return 0;
    }

    Verified with

    cc shiftbits.c -o shiftbits && ./shiftbits |
    tr -cd 01 | perl -nle 'print unpack "H*", pack "B*", scalar reverse $_'

    It's pretty easy to eliminate the variable 'i' from the shift function too.
    Write the loop like this:

    while(siz) {
    int s = *p & 1;
    *p = (*p>>1) | (carry<<(CHAR_BIT-1));
    carry = s;
    --siz;
    ++p;
    }

    Decide for yourself whether that's an improvement or not.

    --
    Alan Curry
    Alan Curry, Oct 27, 2009
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    Alan Curry a écrit :
    > Here's the test case I used, together with my working implementation. The key
    > idea is to set the "carry" variable to be the value that will be shifted into
    > the top bit of the next byte. Set that to 0 before the loop starts, and you
    > don't have to special-case the first byte.


    Right. That is the idea I as missing. Thanks a lot.

    >
    > #include <stdio.h>
    > #include <limits.h>
    >
    > static int Shift(char *p,size_t siz)
    > {
    > size_t i;
    > int carry;
    >
    > carry = 0;
    > for(i=0 ; i<siz ; ++i) {
    > int s = p & 1;
    > p = (p>>1) | (carry<<(CHAR_BIT-1));
    > carry = s;
    > }
    > return carry;
    > }
    >


    It looks cleaner of course.
    >
    > It's pretty easy to eliminate the variable 'i' from the shift function too.
    > Write the loop like this:
    >
    > while(siz) {
    > int s = *p & 1;
    > *p = (*p>>1) | (carry<<(CHAR_BIT-1));
    > carry = s;
    > --siz;
    > ++p;
    > }
    >
    > Decide for yourself whether that's an improvement or not.
    >


    It is an improvement in the sense it looks clearer.

    Thanks again.
    jacob navia, Oct 27, 2009
    #3
  4. On Tue, 27 Oct 2009 17:17:05 -0400, jacob navia <> wrote:

    > Given a bitstring of size siz (in bytes), shift it right by 1 bit.
    > Return the bit that was shifted out
    >
    > static int Shift(char *p,size_t siz)


    static int Shift(unsigned char *p, size_t size)


    1) If p is a (char *p), you'll get incorrect results on any platform
    where "plain char" is signed.

    2) "size" is not a reserved word. Why not call the variable what it
    is? (cf. Dennis Ritchie supposedly saying that his only regret in
    the original design of Unix was using the name "creat" instead of
    "create").

    --
    Morris Keesan --
    Morris Keesan, Oct 28, 2009
    #4
  5. jacob navia <> wrote:
    > Given a bitstring of size siz (in bytes), shift it
    > right by 1 bit. Return the bit that was shifted out
    >
    > static int Shift(char *p,size_t siz)
    > {
    >          int carry;
    >         size_t i;
    >
    >          carry = p[0]&1;
    >          p[0] >>= 1;
    >          for (i=1; i<siz;i++) {
    >                  int s = p&1;
    >                  p = (p >> 1) | (carry << 7);
    >                  if (i < siz-1)
    >                          carry = p[i+1]&1;
    >                  else carry = s;
    >          }
    >          return carry;
    >
    > }


    If you're prepared to limit the code to implementations
    where UINT_MAX > UCHAR_MAX, then just use a shift register...

    #include <limits.h>
    #include <stddef.h>

    int asr(unsigned char *p, size_t z)
    {
    unsigned b;

    for (b = 0; z--; p++)
    {
    b = (b << CHAR_BIT) | *p;
    *p = b >> 1;
    }

    return b & 1;
    }

    --
    Peter
    Peter Nilsson, Oct 28, 2009
    #5
  6. jacob navia

    jacob navia Guest

    Morris Keesan a écrit :
    > On Tue, 27 Oct 2009 17:17:05 -0400, jacob navia <> wrote:
    >
    >> Given a bitstring of size siz (in bytes), shift it right by 1 bit.
    >> Return the bit that was shifted out
    >>
    >> static int Shift(char *p,size_t siz)

    >
    > static int Shift(unsigned char *p, size_t size)
    >
    >
    > 1) If p is a (char *p), you'll get incorrect results on any platform
    > where "plain char" is signed.
    >

    OK. Will change that. Thanks

    > 2) "size" is not a reserved word. Why not call the variable what it
    > is? (cf. Dennis Ritchie supposedly saying that his only regret in
    > the original design of Unix was using the name "creat" instead of
    > "create").
    >


    "siz" is an abbreviation I always use for size for "hysterical reasons"...

    I never thought about it since I am so used to it that I do not even
    realize it is an abbreviation.
    jacob navia, Oct 28, 2009
    #6
  7. jacob navia

    jacob navia Guest

    Peter Nilsson a écrit :
    >
    > If you're prepared to limit the code to implementations
    > where UINT_MAX > UCHAR_MAX, then just use a shift register...
    >
    > #include <limits.h>
    > #include <stddef.h>
    >
    > int asr(unsigned char *p, size_t z)
    > {
    > unsigned b;
    >
    > for (b = 0; z--; p++)
    > {
    > b = (b << CHAR_BIT) | *p;
    > *p = b >> 1;
    > }
    >
    > return b & 1;
    > }
    >
    > --
    > Peter


    Well, that is a very good solution!

    Now that I see this I remember I use this solution in the assembly code
    for the extended precision floats that I have in lcc-win. I am getting
    old, or maybe I am just tired. Thanks a lot for your excellent solution.

    jacob
    jacob navia, Oct 28, 2009
    #7
    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. GGG
    Replies:
    10
    Views:
    12,511
    Donar
    Jul 6, 2006
  2. sarmin kho
    Replies:
    2
    Views:
    816
    A. Lloyd Flanagan
    Jun 15, 2004
  3. Miki Tebeka
    Replies:
    1
    Views:
    432
    Marcin 'Qrczak' Kowalczyk
    Jun 14, 2004
  4. krunalb
    Replies:
    10
    Views:
    899
    Kenneth Brody
    Jan 23, 2007
  5. arnuld

    Shifting bits

    arnuld, Nov 29, 2011, in forum: C Programming
    Replies:
    31
    Views:
    1,403
    Kaz Kylheku
    Dec 1, 2011
Loading...

Share This Page