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

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

Answer 2

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 3

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.