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

I think the answer is a slightly modified application of the getbits example from section 2.9.

Lets break it down as follows:

Let bitstring x be 1 0 1 1 0 0
Let bitstring y be 1 0 1 1 1 1

positions -------->5 4 3 2 1 0

Setting p = 4 and n =3 gives us the bitstring from x which is 0 1 1. It starts at 4 and ends at 2 and spans 3 elements.

What we want to do is to replace 0 1 1 with 1 1 1(the last three elements of bitstring y).

Lets forget about left-shift/right-shift for the moment and visualize the problem as follows:

We need to grab the last three digits from bitstring y which is 1 1 1

Place 1 1 1 directly under positions 4 3 and 2 of bitstring x.

Replace 0 1 1 with 1 1 1 while keeping the rest of the bits intact...

Now lets go into a little more detail...

My first statement was:

We need to grab the last three digits from bitstring y which is 1 1 1

The way to isolate bits from a bitstring is to first start with bitstring that has all 0s. We end up with 0 0 0 0 0 0.

0s have this incredible property where bitwise '&'ing it with another number gives us all 0s and bitwise '|'ing it with another number gives us back that other number.

0 by itself is of no use here...but it tells us that if we '|' the last three digits of y with a '0', we will end up with 1 1 1. The other bits in y don't really concern us here, so we need to figure out a way to zero out those numbers while keeping the last three digits intact. In essence we need the number 0 0 0 1 1 1.

So lets look at the series of transformations required:

Start with  ->  0 0 0 0 0 0
apply ~0    ->  1 1 1 1 1 1
lshift by 3 ->  1 1 1 0 0 0 
apply ~     ->  0 0 0 1 1 1
& with y    ->  0 0 0 1 1 1 & 1 0 1 1 1 1 -> 0 0 0 1 1 1

And this way we have the last three digits to be used for setting purposes...

My second statement was:

Place 1 1 1 directly under positions 4 3 and 2 of bitstring x.

A hint for doing this can be found from the getbits example in section 2.9. What we know about positions 4,3 and 2, can be found from the values p = 4 and n =3. p is the position and n is the length of the bitset. Turns out p+1-n gives us the offset of the bitset from the rightmost bit. In this particular example p+1-n = 4 +1-3 = 2.

So..if we do a left shift by 2 on the string 0 0 0 1 1 1, we end up with 0 1 1 1 0 0. If you put this string under x, you will notice that 1 1 1 aligns with positions 4 3 and 2 of x.

I think I am finally getting somewhere...the last statement I made was..

Replace 0 1 1 with 1 1 1 while keeping the rest of the bits intact...

Lets review our strings now:

x           ->   1 0 1 1 0 0
isolated y  ->   0 1 1 1 0 0

Doing a bitwise or on these two values gives us what we need for this case:

1 1 1 1 0 0 

But this would fail if instead of 1 1 1, we had 1 0 1...so if we need to dig a little more to get to our "silver-bullet"...

Lets look at the above two strings one more time...

x -> bit by bit...1(stays) 0(changes) 1(changes) 1(changes) 0(stays) 0(stays)

So ideally..we need the bitstring 1 x x x 0 0, where the x's will be swapped with 1's. Here's a leap of intuition that will help us..

Bitwise complement of isolated y -> 1 0 0 0 1 1
& this with x gives us           -> 1 0 0 0 0 0
| this with isolated y           -> 1 1 1 1 0 0 (TADA!)

Hope this long post helps people with rationalizing and solving such bitmasking problems...

Thanks