Bitwise setbits function (knr 2-6)

This is a discussion on Bitwise setbits function (knr 2-6) within the C Programming forums, part of the General Programming Boards category; Code: /* getbits: get n bits from position p */ unsigned getbits(unsigned x, int p, int n) { return (x ...

  1. #1
    Insomniac
    Join Date
    Mar 2004
    Posts
    35

    Bitwise setbits function (knr 2-6)

    Code:
    /* getbits: get n bits from position p */
    unsigned getbits(unsigned x, int p, int n) 
    {
    return (x >> (p+1 -n)) & ~(0 << n);
    }
    This is the example in knr, which is what I have to presumeably adapt to the following:

    Write a function getbits(x,p,n,y) that return x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
    Could someone please re-iterate this. Maybe draw a few diagrams to

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Assume x is 01100110 and y is 11010011. With the call setbits ( x, 3, 4, y ), the result is:
    Code:
    x - 0110
    y -     0011
        --------
        01100011
    The function takes x up to position p, then replaces n bits with the rightmost n bits of y. Another example would be (using the same bits) and the call setbits ( x, 4, 2, y ):
    Code:
    x - 011
    y -    11
    x -      110
        --------
        01111110
    Does that help?
    My best code is written with the delete key.

  3. #3
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    I see now! Thank you for answering such a lame question Appreciated.

  4. #4
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    Well, I struggled (still) with the task. I picked the answer off the site, and its below.
    return ((x & ((~0 << (p+1)) | (~(~0 << (p+1-n)))) | ((y & (~(~0 << n)) << (p+1 - n));
    And I've been breaking it up to try and understand.

    (~0 << (p+1))
    complement any 0, and left shift by (p+1) fields.

    (~(~0 << (p+1-n)))
    complement any 0, left shift by (p+1-n), and then complement again back to original value.

    Compare the two with Inclusive OR.

    ...This is where I think I'm wrong. So i try putting it into practise and implementing this... and I get lost.
    Could I be looking to closely?

    Sorry for being a pain in the neck, really would like to understand. And I have tried checking other bitwise explanations, its jsut the implementation that escapes me.


  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    The following is not the easiest thing to look at, but I'm hoping it may help a little.
    Code:
    #include <stdio.h>
    
    #define WYSIWYG(x)   #x, (x)
    const char format[] = "%50s = %08X\n";
    
    /*
     * http://users.powernet.co.uk/eton/kandr2/krx206.html
     *
     * Write a function setbits(x,p,n,y) that returns x with the n
     * bits that begin at position p set to the rightmost n bits of
     * y, leaving the other bits unchanged.
     */
    unsigned setbits(unsigned x, int p, int n, unsigned y)
    {
    #if 1 /* use 0 to comment out */
       printf(format, WYSIWYG(~0));
       putchar('\n');
       printf("p = %d, n = %d\n", p, n);
       printf(format, WYSIWYG(x));
       printf(format, WYSIWYG(y));
       putchar('\n');
       printf(format, WYSIWYG(      (~0 << (p + 1)                           )));
       printf(format, WYSIWYG(                        (~(~0 << (p + 1 - n)))  ));
       printf(format, WYSIWYG(     ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)) ))));
       printf(format, WYSIWYG((x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))))));
       putchar('\n');
       printf(format, WYSIWYG(      ~(~0 << n)                 ));
       printf(format, WYSIWYG( (y & ~(~0 << n))                ));
       printf(format, WYSIWYG(((y & ~(~0 << n)) << (p + 1 - n))));
       putchar('\n');
    #endif
       return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) |
              ((y & ~(~0 << n)) << (p + 1 - n));
    }
    
    int main(void)
    {
       unsigned k = setbits(0x12341234U, 15, 8, 0x56785678U);
       printf(format, WYSIWYG(k));
       return 0;
    }
    
    /* my output
                                                    ~0 = FFFFFFFF
    
    p = 15, n = 8
                                                     x = 12341234
                                                     y = 56785678
    
                                      (~0 << (p + 1) ) = FFFF0000
                                (~(~0 << (p + 1 - n))) = 000000FF
           ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)) )) = FFFF00FF
      (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) = 12340034
    
                                            ~(~0 << n) = 000000FF
                                      (y & ~(~0 << n)) = 00000078
                     ((y & ~(~0 << n)) << (p + 1 - n)) = 00007800
    
                                                     k = 12347834
    */
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  6. #6
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,156
    Originally posted by olbas
    Compare the two with Inclusive OR.
    No, the single | means OR the two calues together:
    Code:
         a = 010011
         b = 110000
    
    a | b = 110011
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  7. #7
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    Thanks for the last note, specifically because I was aware of it, though I was lazy with an explanation, never a good thing, so thanks for bringing this to my attention

    In response to your explanation, the FF's baffled me as to a hidden meaning, though I ran with it and re-read both Prelude's explanation and knr's.

    ~(~0 << (p+1-n))

    I couldn't understand the impact of either side of the expression.

    Now it reads:
    complement bits (p+1-n) from right to left, and then complement the remainder.
    EG:
    11111111
    11111100
    00000011

    Ahh I understand now, even if it doesn't look like it

    Thank you both very much. Really big help.

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    >the FF's baffled me as to a hidden meaning

    I find it easier to follow the hex than the binary.
    Code:
    #include <stdio.h>
    #include <limits.h>
    
    #define WYSIWYG(x)   #x, (x), bitstring(buffer, (x))
    const char format[] = "%48s = %08X = %s\n";
    
    char *bitstring(char *s, unsigned int value)
    {
       unsigned int mask;
       char const letter[2] = { '0', '1' };
       char *start = s;
       for(mask = 1U << ((sizeof(value) * CHAR_BIT) - 1); mask; mask >>= 1)
       {
          *s++ = value & mask ? letter[1] : letter[0];
       }
       *s = 0;
       return start;
    }
    
    /*
     * http://users.powernet.co.uk/eton/kandr2/krx206.html
     *
     * Write a function setbits(x,p,n,y) that returns x with the n
     * bits that begin at position p set to the rightmost n bits of
     * y, leaving the other bits unchanged.
     */
    unsigned setbits(unsigned x, int p, int n, unsigned y)
    {
    #if 1 /* use 0 to comment out */
       char buffer [ sizeof x * CHAR_BIT + 1 ];
       printf(format, WYSIWYG(~0));
       printf("p = %d, n = %d\n", p, n);
       printf(format, WYSIWYG(x));
       printf(format, WYSIWYG(      (~0 << (p + 1)                           )));
       printf(format, WYSIWYG(                        (~(~0 << (p + 1 - n)))  ));
       printf(format, WYSIWYG(     ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))) ));
       printf(format, WYSIWYG((x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))))));
       putchar('\n');
       printf(format, WYSIWYG(y));
       printf(format, WYSIWYG(      ~(~0 << n)                 ));
       printf(format, WYSIWYG( (y & ~(~0 << n))                ));
       printf(format, WYSIWYG(((y & ~(~0 << n)) << (p + 1 - n))));
       putchar('\n');
    #endif
       return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) |
              ((y & ~(~0 << n)) << (p + 1 - n));
    }
    
    int main(void)
    {
       unsigned k;
       char buffer [ sizeof k * CHAR_BIT + 1 ];
       k = setbits(0x12341234U, 15, 8, 0x56785678U);
       printf(format, WYSIWYG(k));
       return 0;
    }
    
    /* my output
                                                  ~0 = FFFFFFFF = 11111111111111111111111111111111
    p = 15, n = 8
                                                   x = 12341234 = 00010010001101000001001000110100
                                    (~0 << (p + 1) ) = FFFF0000 = 11111111111111110000000000000000
                              (~(~0 << (p + 1 - n))) = 000000FF = 00000000000000000000000011111111
          ((~0 << (p + 1)) | (~(~0 << (p + 1 - n)))) = FFFF00FF = 11111111111111110000000011111111
    (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) = 12340034 = 00010010001101000000000000110100
    
                                                   y = 56785678 = 01010110011110000101011001111000
                                          ~(~0 << n) = 000000FF = 00000000000000000000000011111111
                                    (y & ~(~0 << n)) = 00000078 = 00000000000000000000000001111000
                   ((y & ~(~0 << n)) << (p + 1 - n)) = 00007800 = 00000000000000000111100000000000
    
                                                   k = 12347834 = 00010010001101000111100000110100
    */
    Last edited by Dave_Sinkula; 03-26-2004 at 07:00 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #9
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    There's a new method And it does seem more conveniant, and also more helpful with keeping each number base in my head.

    sizeof and limits.h haven't been introduced yet, though I am familiar with them, but I cannot include them in my final answer for the exercise..its cheating you see :P

    The buffer array decleration is different, I didn't know you could use expressions for the elements. Also, the for loop has some interesting arguements.


    Million and one ways to do things in C, you seem to be a good coder, so forgive me if I don't look for errors
    tyvm

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    >Also, the for loop has some interesting arguements.

    Oops -- old code for a quick hack. Currently my preferred "high bit thingy" looks like this for unsigned ints.
    Code:
    #include <stdio.h>
    #include <limits.h>
    
    char *bitstring(char *s, unsigned int value)
    {
       unsigned int mask;
       char *start = s;
       for ( mask = (-1U >> 1) + 1; mask; mask >>= 1 )
       {
          *s++ = "01"[mask & value ? 1 : 0];
       }
       *s = 0;
       return start;
    }
    
    int main(void)
    {
       unsigned k = 0x12341234U;
       char buffer [ sizeof k * CHAR_BIT + 1 ];
       printf("k = %08X = %s\n", k, bitstring(buffer, k));
       return 0;
    }
    
    /* my output
    k = 12341234 = 00010010001101000001001000110100
    */
    >The buffer array decleration is different, I didn't know you could use expressions for the elements.

    As long as it is constant at compile time, its okay for C89.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  11. #11
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    ok this drove me freakin insane, so i hope i can understand and implement this PITA.

    x ^ (~(~0 << n) << p)
    x = 1234 1234
    n = 8
    p = 16
    ~0 = FFFF FFFF

    Step 1: (~0 << n) = FFFF FF00
    Step 2: ~ = 0000 00FF
    Step 3: << p = 0000 FF00

    Step 4: x ^:
    1234 1234
    0000 FF00
    ---------------
    1234 ED34

    Pleaaaase tell me I got that right.

    The solution included (~(~0U << n), the U represents an unsigned int type, it's not neccessary though is it?

  12. #12
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    Exercise:
    Write a function rightrot(x.n) that returns the value of the integer x to the right by n bit positions.
    Given answer:
    Code:
    unsigned rightrot(unsigned x, unsigned n)
    {
        while (n > 0) {
            if ((x & 1) == 1)
                x = (x >> 1) | ~(~0U >> 1);
            else
                x = (x >> 1);
            n--;
        }
        return x;
    My answer:
    Code:
    #include <stdio.h>
    
    unsigned rightrot(unsigned, unsigned);
    int main(void) {
            unsigned x = 12;
            unsigned n = 2;
    
            printf("%u", rightrot(x, n));
            return 0;
            }
    
    unsigned rightrot(unsigned a, unsigned b) {
            return (a >> b);
            }
    Why does it seem like I have done it wrongly.. I did what the exercise requested, yet mine seems somewhat simplier. Any comments on why this is? Obviously error checking is missing.

  13. #13
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by olbas
    Why does it seem like I have done it wrongly.. I did what the exercise requested, yet mine seems somewhat simplier. Any comments on why this is?
    The test values you use don't demonstrate any difference between a bitwise rotation and a bitwise shift. If you had chosen different values, then the difference would be more noticeable.
    Code:
    #include <stdio.h>
    
    unsigned rightrot1(unsigned x, unsigned n)
    {
       while ( n > 0 )
       {
          if ( (x & 1) == 1 )
             x = (x >> 1) | ~(~0U >> 1);
          else
             x = (x >> 1);
          n--;
       }
       return x;
    }
    
    unsigned rightrot2(unsigned a, unsigned b)
    {
       return(a >> b);
    }
    
    int main(void)
    {
       unsigned result;
       unsigned x = 12;
       unsigned n = 2;
       
       result = rightrot1(x, n);
       printf("rightrot1(%u, %u) = %u = %x\n", x, n, result, result);
       result = rightrot2(x, n);
       printf("rightrot2(%u, %u) = %u = %x\n", x, n, result, result);
       
       x = 0x1234U;
       n = 8;
       result = rightrot1(x, n);
       printf("rightrot1(%u, %u) = %u = %x\n", x, n, result, result);
       result = rightrot2(x, n);
       printf("rightrot2(%u, %u) = %u = %x\n", x, n, result, result);
       return 0;
    }
    
    /* my output
    rightrot1(12, 2) = 3 = 3
    rightrot2(12, 2) = 3 = 3
    rightrot1(4660, 8) = 872415250 = 34000012
    rightrot2(4660, 8) = 18 = 12
    */
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  14. #14
    Insomniac
    Join Date
    Mar 2004
    Posts
    35
    Ahh I get that now, (a >> b) right shifts the left-most 1-bit n places and returns the value. It doesn't shift all 1-bits.

    This is why people use loops to feed test values and not just a single static value.

    You know your stuff! Thanks! Another lesson learned

  15. #15
    Registered User
    Join Date
    Mar 2010
    Posts
    94
    Please answer me these qeestions:

    x ^ (~(~0 << n) << p)
    x = 1234 1234
    n = 8
    p = 16
    ~0 = FFFF FFFF

    Step 1: (~0 << n) = FFFF FF00
    Step 2: ~ = 0000 00FF
    Step 3: << p = 0000 FF00

    Step 4: x ^:
    1234 1234
    0000 FF00
    ---------------
    1234 ED34

    I would like someone to explain me the above steps with binary numbers as I am unable to understand it with hexadecimal numbers

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  2. Message class ** Need help befor 12am tonight**
    By TransformedBG in forum C++ Programming
    Replies: 1
    Last Post: 11-29-2006, 10:03 PM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  4. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 01:53 AM
  5. Question..
    By pode in forum Windows Programming
    Replies: 12
    Last Post: 12-19-2004, 06:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21