Thread: Exercise 2-6 K&R help

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    9

    Exercise 2-6 K&R help

    hello,

    I have started learning c with K&R 2nd edition, and have stumbled along the question.
    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.

    I have found a solution from here but i do not understand it.

    perhaps i am not understanding the task....

    thanks in advance

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,625
    Yes, "a" solution.

    Like a lot of short C problems, it is possible to reduce them to pretty cryptic versions for those with a great deal of experience.

    So try and solve it for yourself rather than hunting down someone elses answers.

    http://cboard.cprogramming.com/showthread.php?t=81960
    Seems to be trying the same thing.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,212
    Quote Originally Posted by allix
    hello,

    I have started learning c with K&R 2nd edition, and have stumbled along the question.
    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.

    I have found a solution from here but i do not understand it.

    perhaps i am not understanding the task....

    thanks in advance
    Well I don't see how anybody can understand that line of code without spending a few years researching it.

    Code:
    return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) | ((y & ~(~0 << n)) << (p + 1 - n));

  4. #4
    Registered User
    Join Date
    Aug 2006
    Posts
    9
    Quote Originally Posted by Brian
    Well I don't see how anybody can understand that line of code without spending a few years researching it.

    Code:
    return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) | ((y & ~(~0 << n)) << (p + 1 - n));
    was that sarcastic ?

  5. #5
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    No. It's an exagerattion. You should try to code a clear readable solution.

  6. #6
    Registered User
    Join Date
    Aug 2006
    Posts
    9
    Code:
    return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) | ((y & ~(~0 << n)) << (p + 1 - n));
    the only vague idea that i understand of this is
    return (x & ((~0 << (p + 1)) | (~(~0 << (p + 1 - n))))) // x is with the n bits starting at p position
    | ((y & ~(~0 << n)) << (p + 1 - n)) /// meanwhile y is pushed more to the left making x goto right side of y


    i hope that makes sense

  7. #7
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Split it up some:
    Code:
    // Assume  x = 10010011 (binary), p = 3 (decimal), n = 2 (decimal), y = 11001010 (binary)
    // Also assume rightmost bit (LSB) is position 1.
    
    uint8_t setbits(uint8_t x, uint8_t p, uint8_t n, uint8_t y)
    {
      uint8_t mask;
      uint8_t temp;
    
      mask = ~0;            // All bits set  (mask = 11111111)
      mask >>= 8 - n;     // n bits set in lowest position (mask = 00000011)
    
      temp = y & mask;  // set to first n bits of y (temp = 00000010)
      temp <<= p - 1;    // set to n bits of y at position p (temp = 00001000)
    
      mask <<= p - 1;    // n bits set at position p (mask = 00001100)
    
      x &= ~mask;         // n bits at position p cleared (x = 10010011)
      x |= temp;             // x set to first n bits of y at position p (x = 10011011)
    
      return x;
    }
    Last edited by itsme86; 08-17-2006 at 02:51 PM.
    If you understand what you're doing, you're not learning anything.

  8. #8
    Registered User
    Join Date
    Aug 2006
    Posts
    9
    Quote Originally Posted by itsme86
    Split it up some:
    Code:
    // Assume  x = 10010011 (binary), p = 3 (decimal), n = 2 (decimal), y = 11001010 (binary)
    // Also assume "first bits" means least significant
    
    uint8_t setbits(uint8_t x, uint8_t p, uint8_t n, uint8_t y)
    {
      uint8_t mask;
      uint8_t temp;
    
      mask = ~0;            // All bits set  (mask = 11111111)
      mask >>= 8 - n;     // n bits set in lowest position (mask = 00000011)
    
      temp = y & mask;  // set to first n bits of y (temp = 00000010)
      temp <<= p - 1;    // set to n bits of y at position p (temp = 00001000)
    
      mask <<= p - 1;    // n bits set at position p (mask = 00001100)
    
      x &= ~mask;         // n bits at position p cleared (x = 10010011)
      x |= temp;             // x set to first n bits of y at position p (x = 10011011)
    
      return x;
    }
    i am not going to pretend i follow you


    mask = ~0; // All bits set (mask = 11111111) // i understand that
    mask >>= 8 - n; // n bits set in lowest position (mask = 00000011) // oh , i thought that would give (mask = 00000000) ?

    and the rest you have lost me

    sorry

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,625
    Try and solve it for yourself then - that is after all the point of exercises.

    There's no point just reading the book and googling for answers, then moaning that you don't understand someones example answer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >and the rest you have lost me
    So pull out your trusty reference, your trusty debugger, your trusty pencil and paper, and get unlost. When a programmer looks at unfamiliar code, he doesn't divine the meaning somehow, he trudges through each part and figures it out. You need to learn how to do that, because it's a huge part of programming.
    My best code is written with the delete key.

  11. #11
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    mask >>= 8 - n; // n bits set in lowest position (mask = 00000011) // oh , i thought that would give (mask = 00000000) ?
    We assume n is 2 so you're right shifting the mask (which is currently 11111111) 6 times (8 - 2 = 6).

    1 time: 01111111
    2 times: 00111111
    3 times: 00011111
    4 times: 00001111
    5 times: 00000111
    6 times: 00000011

    I'm not sure how to break down the code much more than that. You might need to do some review of bit operators if you're still confused.
    If you understand what you're doing, you're not learning anything.

  12. #12
    Registered User
    Join Date
    Aug 2006
    Posts
    9
    Quote Originally Posted by itsme86
    We assume n is 2 so you're right shifting the mask (which is currently 11111111) 6 times (8 - 2 = 6).

    1 time: 01111111
    2 times: 00111111
    3 times: 00011111
    4 times: 00001111
    5 times: 00000111
    6 times: 00000011

    I'm not sure how to break down the code much more than that. You might need to do some review of bit operators if you're still confused.
    oh ok, thanks

  13. #13
    Registered User
    Join Date
    Aug 2006
    Posts
    9
    my second attempt , sorry for drawing this out ...

    Quote Originally Posted by itsme86
    Split it up some:
    Code:
    // Assume  x = 10010011 (binary), p = 3 (decimal), n = 2 (decimal), y = 11001010 (binary)
    // Also assume rightmost bit (LSB) is position 1.
    
    uint8_t setbits(uint8_t x, uint8_t p, uint8_t n, uint8_t y)
    {
      uint8_t mask;
      uint8_t temp;
    
      mask = ~0;            // All bits set  (mask = 11111111)
      mask >>= 8 - n;     // n bits set in lowest position (mask = 00000011)
    
      temp = y & mask;  // set to first n bits of y (temp = 00000010) // if i follow this it means the first 2 bits of y aka 4 decimal?
      temp <<= p - 1;    // set to n bits of y at position p (temp = 00001000)// as  mask >>= 8 - n; occupies 2 bits (11) we move temp two places to the left ?
    
      mask <<= p - 1;    // n bits set at position p (mask = 00001100) // we move  mask >>= 8 - n; 2 places to the left ? i am not sure why as its -1 ?
    
      x &= ~mask;         // n bits at position p cleared (x = 10010011) // how comes x is restored to its original value? 
      x |= temp;             // x set to first n bits of y at position p (x = 10011011) // i am not confident on what you did here
    
      return x;
    }

  14. #14
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Not quite.
    // as mask >>= 8 - n; occupies 2 bits (11) we move temp two places to the left ?
    It has nothing to do with the mask or the constant value 8. p is 3 so it shifts left 2 times.
    // we move mask >>= 8 - n; 2 places to the left ? i am not sure why as its -1 ?
    Again, nothing to do with the mask or the constant value 8. It's minus 1 because the mask is already at position 1. So if p is 1 you want to shift it 0 times. If p is 2 you want to shift it 1 time, etc.
    // how comes x is restored to its original value?
    It's not restored. It just so happens that that the 3rd and 4th bits in x are already 0 so clearing them doesn't change the value in this example. It's still a required step for the algorithm to work in a general sense.
    // i am not confident on what you did here
    This is a very straightforward bitwise-OR. I recommend you read up on bitwise operators.
    If you understand what you're doing, you're not learning anything.

  15. #15
    Registered User
    Join Date
    Aug 2006
    Posts
    9
    Quote Originally Posted by itsme86
    It has nothing to do with the mask or the constant value 8. p is 3 so it shifts left 2 times.
    .
    ok.. to give another scenerio

    temp <<= p -2; // set to n bits of y at position p (temp = 00000100)
    would that be correct?

    Quote Originally Posted by itsme86
    Again, nothing to do with the mask or the constant value 8. It's minus 1 because the mask is already at position 1. So if p is 1 you want to shift it 0 times. If p is 2 you want to shift it 1 time, etc.
    .
    mask <<= p - 2; // n bits set at position p (mask = 00000110)
    also, would that be correct?

    Quote Originally Posted by itsme86
    It's not restored. It just so happens that that the 3rd and 4th bits in x are already 0 so clearing them doesn't change the value in this example. It's still a required step for the algorithm to work in a general sense.
    .
    I am not sure what you mean by clear, the two number concerned are the following, right?
    mask =
    00001100
    x =
    10010011

    what should i do with them?

    Quote Originally Posted by itsme86
    This is a very straightforward bitwise-OR. I recommend you read up on bitwise operators.
    x =
    10010011
    temp =
    00001000
    10011011

    i believe thats how the | works , if one of bits compared is one then the result is 1 ?

    I apologise for the odd formating, in order to line up the numbers only the Aligning tool would work, using the space bar would have no effect.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with K&R Book Exercise
    By Alejandrito in forum C Programming
    Replies: 5
    Last Post: 03-11-2008, 01:24 PM
  2. K&R Exercise 1-14
    By Lee134 in forum C Programming
    Replies: 3
    Last Post: 02-16-2006, 11:20 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Help with K&R Exercise 1.13
    By Yannis in forum C Programming
    Replies: 2
    Last Post: 09-21-2003, 02:51 PM
  5. k&r exercise 1-9
    By xion in forum C Programming
    Replies: 14
    Last Post: 07-15-2003, 06:01 PM