k&r exercise confusion with bit-operations

Question

The exercise is: 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.

My attempt at a solution is:

#include <stdio.h>

unsigned setbits(unsigned, int, int, unsigned);

int main(void)
{
    printf("%u\n", setbits(256, 4, 2, 255));
    return 0;
}

unsigned setbits(unsigned x, int p, int n, unsigned y)
{
    return (x >> (p + 1 - n)) | (1 << (n & y));
}

It's probably incorrect, but am I on the right path here? If not, what am I doing wrong? I'm unsure as to why I don't perfectly understand this, but I spent about an hour trying to come up with this.

Thanks.

Answer 1

Here's your algorithm:

1. If n is 0, return x.
2. Take 1, and left shift it n times and then subtract 1. Call this mask.
3. Left shift mask p times call this mask2.
4. And x with the inverse of mask2. And y with mask, and left shift p times.
5. Or the results of those two operations, and return that value.

Answer 2

Note that ~0 << i gives you a number with the least significant i bits set to 0, and the rest of the bits set to 1. Similarly, ~(~0 << i) gives you a number with the least significant i bits set to 1, and the rest to 0.

Now, to solve your problem:

1. First, you want a number that has all the bits except the n bits that begin at position p set to the bits of x. For this, you need a mask that comprises of 1 in all the places except the n bits beginning at position p:
   1. this mask has the topmost (most significant) bits set, starting with the bit at position p+1.
   2. this mask also has the least significant p+1-n bits set.
2. Once you have the above mask, & of this mask with x will give you the number you wanted in step 1.
3. Now, you want a number that has the least significant n bits of y set, shifted left p+1-n bits.
   1. You can easily make a mask that has only the least significant n bits set, and & it with y to extract y's least significant n bits.
   2. Then, you can shift this number by p+1-n bits.
4. Finally, you can bitwise-or (|) the results of step 2 and 3.2 to get your number.

Clear as mud? :-)

(The above method should be independent of the size of the numbers, which I think is important.)

Edit: looking at your effort: n & y doesn't do anything with n bits. For example, if n is 8, you want the last 8 bits of y, but n & y will just pick the 4th bit of y (8 in binary is 1000). So you know that can't be right. Similarly, right-shifting x p+1-n times gives you a number that has the most significant p+1-n bits set to zero and the rest of the bits are made of the most significant bits of x. This isn't what you want either.