Exercise 2-6

This exercise may look daunting at first, so let us try breaking it down and see what it is really asking for.

Imagine x is 10101010_binary, y is 01010101_binary, p is 5₁₀, and n is 4₁₀. What we need to do is replace the four bits starting at position five—10101010—with the last four bits of y—0101. So the value returned should be 10010110_binary.

Let us break this process into steps. The first thing we need to do is replace the four bits with zeros. In order to do this, we use the AND operator as follows: 10101010binary & 11000011binary. Obviously, the bitmask 11000011 only works for this specific scenario and for other values of n and p, we would need a different mask, so let us take a look at how we will generate the bitmask in terms of n and p.

We start with ~0 (11111111_binary). We then shift it n bits to the left. Doing this changes the rightmost n bits to zeros (11110000.) Next, we invert the bits (00001111) and then shift them p + 1 - n bits to the left (00111100.) We use p + 1 because the rightmost bit has position zero. Finally, we invert the bits (11000011.) Putting this all together, we get the code ~(~(~0 << n) << (p + 1 - n))) to represent our bitmask and the statement x & ~(~(~0 << n) << (p + 1 - n))) to set the necessary bits to zeros.

Next, we have to move the four bits in y to the correct location and use the OR operator to combine the two sets of bits: 10000010binary | 00010100binary. Again, let us see how we can achieve this step-by-step using the bitwise operations. First, we need to filter the last n bits of y using the bitmask 00001111. To create the mask in terms of n, we shift ~0 (11111111_binary) n bits to the left (11110000) and then invert the bits (00001111.) We then use the AND operator to filter the last n bits from y (00000101). This results in the code y & ~(~0 << n). Finally, we shift the bits p + 1 - n bits to the left (00010100) and use the OR operator with the two sets of bits.

    /* setbits:  return x with rightmost n bits from y starting from p */
    unsigned setbits(unsigned x, int p, int n, unsigned y)
    {
        return (x & ~(~(~0U << n) << (p+1-n))) | ((y & ~(~0U << n)) << (p+1-n));
    }

Note: in the example we used to understand how to code our function, we assumed we were computing on a single byte (eight bits); however, in the actual function we use unsigned int, so the function works on what is most likely a 32-bit string (this does depend on the implementation.)

Note: using unsigned int means that the numbers used actually represent the bit strings (in two's complement machines, the place value of the leftmost bit is -128 for signed ints.)